Problems

Practice is the only way to master Bit Manipulation. The following problems are sorted by difficulty and cover the most common patterns you’ll encounter in interviews.

Easy Problems

1. Single Number

Brief: Find the element that appears once in an array where every other element appears twice.
Why this pattern?: The XOR operation has a self-inverse property: x ^ x = 0 and x ^ 0 = x.
Key Insight: XORing all numbers together will cancel out the duplicates, leaving only the unique number.

Visual Explanation:

  graph TD
    A["Input: 4, 1, 2, 1, 2"]

    subgraph Computation
    S1["0 ^ 4 = 4"]
    S2["4 ^ 1 = 5"]
    S3["5 ^ 2 = 7"]
    S4["7 ^ 1 = 6  (Removes 1)"]
    S5["6 ^ 2 = 4  (Removes 2)"]
    end

    A --> S1 --> S1 --> S2 --> S3 --> S4 --> S5

    S5 --> Result["Result: 4"]

    style Result fill:#e8f5e9,stroke:#2e7d32

/**
 * Time: O(N)
 * Space: O(1)
 */
function singleNumber(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
}

def single_number(nums: List[int]) -> int:
    result = 0
    for num in nums:
        result ^= num
    return result

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

func singleNumber(nums []int) int {
    result := 0
    for _, num := range nums {
        result ^= num
    }
    return result
}

def single_number(nums)
  result = 0
  nums.each { |num| result ^= num }
  result
end

2. Number of 1 Bits

Brief: Write a function that takes an unsigned integer and returns the number of ‘1’ bits it has (“Hamming Weight”).
Why this pattern?: We need to count set bits efficiently.
Key Insight: n & (n - 1) always clears the least significant bit set to 1. Repeatedly performing this counts the bits faster than shifting.

Visual Explanation:

  graph TD
    Start["n = 11 (1011)"] --> Op1["n & n-1"]
    Op1 --> Step1["n = 10 (1010)"]
    Step1 --> Op2["n & n-1"]
    Op2 --> Step2["n = 8 (1000)"]
    Step2 --> Op3["n & n-1"]
    Op3 --> Step3["n = 0 (0000)"]

    Step3 --> Done["Count = 3"]

/**
 * Time: O(k) where k is number of set bits
 * Space: O(1)
 */
function hammingWeight(n) {
    let count = 0;
    while (n !== 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

def hammingWeight(n: int) -> int:
    count = 0
    while n:
        n &= (n - 1)
        count += 1
    return count

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;
        while (n) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
};

func hammingWeight(num uint32) int {
    count := 0
    for num != 0 {
        num &= (num - 1)
        count++
    }
    return count
}

def hamming_weight(n)
  count = 0
  while n != 0
    n &= (n - 1)
    count += 1
  end
  count
end

3. Missing Number

Brief: Given an array nums containing n distinct numbers in the range [0, n], return the missing number.
Why this pattern?: Similar to Single Number, XORing index i with value nums[i] helps cancel out pairs.
Key Insight: XOR all indices 0..n and all values in nums. The missing number will remain.

Visual Explanation:

  graph TD
    Indices["Indices: 0, 1, 2, 3"]
    Values["Values: 3, 0, 1"]

    subgraph XOR_Operation ["XOR Operation"]
    X["0^0 ^ 1^1 ^ 3^3 ^ 2"]
    end

    Indices --> X
    Values --> X
    X --> Result["Result: 2"]

    style Result fill:#fff9c4,stroke:#fbc02d

/**
 * Time: O(N)
 * Space: O(1)
 */
function missingNumber(nums) {
    let xor = nums.length;
    for (let i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

def missing_number(nums: List[int]) -> int:
    xor = len(nums)
    for i, num in enumerate(nums):
        xor ^= i ^ num
    return xor

class Solution {
    public int missingNumber(int[] nums) {
        int xor = nums.length;
        for (int i = 0; i < nums.length; i++) {
            xor ^= i ^ nums[i];
        }
        return xor;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int xorSum = nums.size();
        for (int i = 0; i < nums.size(); i++) {
            xorSum ^= i ^ nums[i];
        }
        return xorSum;
    }
};

func missingNumber(nums []int) int {
    xor := len(nums)
    for i, num := range nums {
        xor ^= i ^ num
    }
    return xor
}

def missing_number(nums)
  xor = nums.length
  nums.each_with_index do |num, i|
    xor ^= i ^ num
  end
  xor
end

Medium Problems

4. Counting Bits

Brief: Given n, return an array of length n + 1 where each element is the number of 1s in its binary representation.
Why this pattern?: Dynamic Programming merges with Bit Manipulation here.
Key Insight: The number of bits in i is the number of bits in i >> 1 plus i & 1.
- dp[i] = dp[i >> 1] + (i & 1)

Visual Explanation:

  graph LR
    A["i = 5 (101)"]
    B["i >> 1 = 2 (10)"]
    C["i & 1 = 1"]

    B -->|Check DP Table| D["dp of 2 is 1"]
    D --> E["1 + 1 = 2"]
    C --> E
    E --> F["dp of 5 is 2"]

/**
 * Time: O(N)
 * Space: O(N)
 */
function countBits(n) {
    const dp = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        dp[i] = dp[i >> 1] + (i & 1);
    }
    return dp;
}

def countBits(n: int) -> List[int]:
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp

class Solution {
    public int[] countBits(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
}

class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> dp(n + 1);
        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i >> 1] + (i & 1);
        }
        return dp;
    }
};

func countBits(n int) []int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = dp[i >> 1] + (i & 1)
    }
    return dp
}

def count_bits(n)
  dp = Array.new(n + 1, 0)
  (1..n).each do |i|
    dp[i] = dp[i >> 1] + (i & 1)
  end
  dp
end

5. Reverse Bits

Brief: Reverse the bits of a given 32 bits unsigned integer.
Why this pattern?: Requires direct manipulation of bit positions.
Key Insight: Iterate 32 times. Extract the i-th bit of inputs and place it at the 31-i position of the output.

Visual Explanation:

  graph TD
    Input["Input: ...0011"]

    subgraph Iteration
    Bit0["Bit 0: 1"] -->|Shift to 31| Out31["Output Bit 31: 1"]
    Bit1["Bit 1: 1"] -->|Shift to 30| Out30["Output Bit 30: 1"]
    end

    Out31 --> Result
    Out30 --> Result["Result: 1100..."]

/**
 * Time: O(1) - Always 32 iterations
 * Space: O(1)
 */
function reverseBits(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        const bit = (n >> i) & 1;
        result = (result << 1) | bit;
    }
    // Force unsigned in JS
    return result >>> 0;
}

def reverseBits(n: int) -> int:
    result = 0
    for i in range(32):
        bit = (n >> i) & 1
        result = (result << 1) | bit
    return result

public class Solution {
    // Treat n as unsigned
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            // Get last bit of n
            int bit = n & 1;
            // Shift result left to make room
            result = (result << 1) | bit;
            // Shift n right to process next bit
            n >>= 1;
        }
        return result;
    }
}

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
};

func reverseBits(num uint32) uint32 {
    var result uint32 = 0
    for i := 0; i < 32; i++ {
        result = (result << 1) | (num & 1)
        num >>= 1
    }
    return result
}

def reverse_bits(n)
  result = 0
  32.times do
    result = (result << 1) | (n & 1)
    n >>= 1
  end
  result
end

6. Sum of Two Integers

Brief: Add two integers a and b without using + or -.
Why this pattern?: Simulates how hardware adders work.
Key Insight:
- Sum without carry is a ^ b.
- Carry is (a & b) << 1.
- Iterate until carry is 0.

Visual Explanation:

  graph TD
    A["A: 01, B: 11"]
    XOR["XOR: 10"]
    AND["AND: 01"]
    Carry["Carry << 1: 10"]

    A --> XOR
    A --> AND --> Carry

    Loop["New A: 10, New B: 10"]
    XOR2["XOR: 00"]
    AND2["AND: 10"]
    Carry2["Carry << 1: 100"]

    Loop --> XOR2
    Loop --> AND2 --> Carry2

    Final["Final Result: 100 (4)"]

/**
 * Time: O(1)
 * Space: O(1)
 */
function getSum(a, b) {
    while (b !== 0) {
        const carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

def getSum(a: int, b: int) -> int:
    # Python has infinite integers, so we need masking for 32-bit simulation
    mask = 0xFFFFFFFF

    while b != 0:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask

    # If a is negative in 32-bit world
    if a > 0x7FFFFFFF:
        a = ~(a ^ mask)
    return a

class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            // Use unsigned to prevent overflow runtime errors in C++
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = (int)carry;
        }
        return a;
    }
};

func getSum(a int, b int) int {
    for b != 0 {
        carry := (a & b) << 1
        a = a ^ b
        b = carry
    }
    return a
}

def get_sum(a, b)
  # Ruby handles large integers automatically,
  # but for strict 32-bit simulation we would need masks.
  # For simple addition logic:
  while b != 0
    carry = (a & b) << 1
    a = a ^ b
    b = carry
  end
  a
end

Recommended Study Order

Start with Single Number to understand the XOR cancellation trick.
Move to Number of 1 Bits to master n & (n - 1).
Practice Counting Bits to see how bit patterns relate to DP.
Finish with Sum of Two Integers to understand hardware-level addition.