Bit Manipulation: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Bit Manipulation: Complete Guide with XOR and Bit Tricks

Welcome to the practice problems for bit manipulation. If you need a refresher on the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems build on each other, so the sequence matters more than the individual solutions.

Single Number teaches the XOR self-inverse property in its purest form. One operation, one cancellation. Master this before moving on.
Number of 1 Bits introduces n & (n - 1), a trick that reappears across many bit manipulation problems.
Missing Number extends the Single Number idea to a range detection problem by XORing indices with values.
Counting Bits merges DP with bit manipulation, showing how i >> 1 reveals the bit pattern relationship between consecutive numbers.
Reverse Bits tests whether you can handle bit positions and loop boundaries cleanly through a brute-force reconstruction.
Sum of Two Integers simulates the hardware adder with XOR for sum and AND for carry. This is the densest algorithm in the set.
Maximum XOR of Two Numbers uses a greedy bit-by-bit approach with a hash set, combining bit tricks with search.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Single Number

LeetCode 136 | Difficulty: Easy

Brief: Find the element that appears once in an array where every other element appears twice.

Why this pattern: XOR has a self-inverse property: x ^ x = 0 and x ^ 0 = x. XORing all numbers together cancels the duplicates and leaves the unique element.

Key Insight: Order does not matter. XOR is commutative and associative, so pairs cancel regardless of where they appear.

Visual:

    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"]
    S5["6 ^ 2 = 4"]
    end

    A --> S1 --> S2 --> S3 --> S4 --> S5
    S5 --> Result["Result: 4"]

Code:

var singleNumber = function(nums) {
    let result = 0;
    for (const num of nums) {
        result ^= num;
    }
    return result;
};

The entire algorithm is the XOR loop. No extra data structures, no conditionals. Each duplicate pair produces 0 and the unique value is what remains. This is the template for all XOR-cancellation problems.

2. Number of 1 Bits

LeetCode 191 | Difficulty: Easy

Brief: Return the number of 1 bits in the binary representation of an unsigned integer (Hamming weight).

Why this pattern: Counting set bits is a common subproblem, and n & (n - 1) clears the lowest set bit in a single operation. Each iteration removes one 1-bit, so the loop runs exactly k times for k set bits.

Key Insight: Instead of shifting through all 32 bits, Kernighan’s algorithm skips over the zeros and jumps directly to each 1-bit.

Visual:

    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"]

Code:

var hammingWeight = function(n) {
    let count = 0;
    while (n !== 0) {
        n &= (n - 1);
        count++;
    }
    return count;
};

Each iteration of the loop removes the lowest set bit. The loop runs exactly as many times as there are 1-bits, making this faster than iterating through all 32 bits when the number is sparse.

3. Missing Number

LeetCode 268 | Difficulty: Easy

Brief: Given an array of n distinct numbers from the range [0, n], find the one number that is missing.

Why this pattern: XOR an element with itself produces 0. By XORing every index and every value together, each matching index-value pair cancels out. The remaining value is the missing number.

Key Insight: The same XOR accumulator from Single Number works here. You just XOR in both the indices and the values.

Visual:

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

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

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

Code:

var missingNumber = function(nums) {
    let xor = nums.length;
    for (let i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
};

The accumulator starts with n (the length of the array) because the range goes from 0 to n inclusive. Every index i pairs with its corresponding value nums[i]. If all numbers were present, every pair would cancel to 0. The missing number is the value that never got paired.

Medium Problems

4. Counting Bits

LeetCode 338 | Difficulty: Medium

Brief: Given n, return an array of length n + 1 where each element is the number of 1 bits in its binary representation.

Why this pattern: The number of bits in i equals the number of bits in i » 1 (which drops the least significant bit) plus i & 1 (which is the dropped bit). This recurrence lets you compute all counts in linear time with no per-number shifting.

Key Insight: This is a DP problem where the subproblem is i » 1, which is always smaller than i. The recurrence is dp[i] = dp[i » 1] + (i & 1).

Visual:

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

    B --> D["dp[2] = 1"]
    D --> E["1 + 1 = 2"]
    C --> E
    E --> F["dp[5] = 2"]

Code:

var countBits = function(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;
};

The recurrence exploits the fact that right-shifting by one removes the least significant bit. If you already know the count for i » 1, you only need to add back the bit you removed. This avoids calling a separate countSetBits function for every number.

5. Reverse Bits

LeetCode 190 | Difficulty: Medium

Brief: Reverse the bits of a given 32-bit unsigned integer.

Why this pattern: This is a direct bit-position manipulation problem. Each bit at position i in the input must move to position 31 - i in the output.

Key Insight: Build the result bit by bit. Extract the least significant bit of the remaining input, shift it into the result from the most significant side, and repeat for all 32 positions.

Visual:

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

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

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

Code:

var reverseBits = function(n) {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        const bit = (n >> i) & 1;
        result = (result << 1) | bit;
    }
    return result >>> 0;
};

public class Solution {
    public int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            // Extract the least significant bit of the
            // remaining input to place at the next
            // most significant position in the result
            result = (result << 1) | (n & 1);
            n >>= 1;
        }
        return result;
    }
}

Each iteration picks off the lowest bit of the remaining input and appends it to the result from the high side. By the time all 32 bits have been extracted from the input, the result holds them in reverse order. The JavaScript version uses >>> 0 to coerce the result to an unsigned 32-bit integer.

6. Sum of Two Integers

LeetCode 371 | Difficulty: Medium

Brief: Add two integers a and b without using the + or - operators.

Why this pattern: XOR computes the sum without carry. AND computes the carry positions. Shifting the carry left by one aligns it with the next bit position. Repeating until carry is 0 produces the full sum.

Key Insight: The addition breaks down into two independent operations. Bitwise XOR gives the sum of each bit ignoring carries. Bitwise AND captures where a carry is generated, which must be added to the next higher bit.

Visual:

    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)"]

Code:

var getSum = function(a, b) {
    while (b !== 0) {
        const carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
};

The loop terminates because carry moves a set bit to the left on each iteration. After at most 32 iterations, carry reaches 0 and the full sum is in a. The Python version needs a 32-bit mask because Python integers are arbitrarily large, so the carry would never naturally overflow to 0.

Hard Problems

7. Maximum XOR of Two Numbers in an Array

LeetCode 421 | Difficulty: Hard

Brief: Given an integer array, find the maximum result of nums[i] ^ nums[j] for any two elements.

Why this pattern: Instead of checking all pairs in

O(N^2)

, you build the answer one bit at a time from most significant to least using a greedy approach with a hash set.

Key Insight: To check if a prefix p is achievable as an XOR of two numbers, store all prefixes of the current bit length in a hash set. For each prefix, check if prefix ^ desired_result also exists in the set. If it does, that bit can be set in the result.

Visual:

    graph TD
    I["Start result = 0"] --> B["Try bit 31"]
    B --> P["Build prefixes with 31 bits"]
    P --> D{"Pair with XOR >= candidate?"}
    D -->|Yes| S["Set bit in result"]
    D -->|No| L["Keep result"]
    S --> N["Try bit 30"]
    L --> N["..."]
    N --> F["Return final result"]

Code:

var findMaximumXOR = function(nums) {
    let maxResult = 0;
    let mask = 0;

    for (let i = 31; i >= 0; i--) {
        mask = mask | (1 << i);
        const prefixes = new Set();
        for (const num of nums) {
            prefixes.add(num & mask);
        }

        const candidate = maxResult | (1 << i);
        for (const prefix of prefixes) {
            if (prefixes.has(prefix ^ candidate)) {
                maxResult = candidate;
                break;
            }
        }
    }
    return maxResult;
};

class Solution:
    def findMaximumXOR(self, nums: List[int]) -> int:
        max_result = 0
        mask = 0

        for i in range(31, -1, -1):
            mask |= (1 << i)
            prefixes = {num & mask for num in nums}

            candidate = max_result | (1 << i)
            for prefix in prefixes:
                if (prefix ^ candidate) in prefixes:
                    max_result = candidate
                    break

        return max_result

class Solution {
    public int findMaximumXOR(int[] nums) {
        int maxResult = 0;
        int mask = 0;

        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            Set<Integer> prefixes = new HashSet<>();
            for (int num : nums) {
                prefixes.add(num & mask);
            }

            int candidate = maxResult | (1 << i);
            for (int prefix : prefixes) {
                if (prefixes.contains(prefix ^ candidate)) {
                    maxResult = candidate;
                    break;
                }
            }
        }
        return maxResult;
    }
}

class Solution {
public:
    int findMaximumXOR(vector<int>& nums) {
        int maxResult = 0;
        int mask = 0;

        for (int i = 31; i >= 0; i--) {
            mask |= (1 << i);
            unordered_set<int> prefixes;
            for (int num : nums) {
                prefixes.insert(num & mask);
            }

            int candidate = maxResult | (1 << i);
            for (int prefix : prefixes) {
                if (prefixes.count(prefix ^ candidate)) {
                    maxResult = candidate;
                    break;
                }
            }
        }
        return maxResult;
    }
};

func findMaximumXOR(nums []int) int {
    maxResult := 0
    mask := 0

    for i := 31; i >= 0; i-- {
        mask |= (1 << i)
        prefixes := make(map[int]bool)
        for _, num := range nums {
            prefixes[num&mask] = true
        }

        candidate := maxResult | (1 << i)
        for prefix := range prefixes {
            if prefixes[prefix^candidate] {
                maxResult = candidate
                break
            }
        }
    }
    return maxResult
}

def find_maximum_xor(nums)
    max_result = 0
    mask = 0

    31.downto(0) do |i|
        mask |= (1 << i)
        prefixes = {}
        nums.each { |num| prefixes[num & mask] = true }

        candidate = max_result | (1 << i)
        prefixes.each_key do |prefix|
            if prefixes[prefix ^ candidate]
                max_result = candidate
                break
            end
        end
    end
    max_result
end

This algorithm builds the answer bit by bit from the most significant bit down. At each step it checks whether the current candidate prefix can be formed by XORing two numbers in the array. The hash set stores the prefixes of all numbers at the current bit length. If two numbers have prefixes that XOR to the candidate, the current bit can be set. The algorithm runs in

O(N log max)

time (32 iterations over N elements) with

O(N)

space for the hash set.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These seven problems cover the full range of bit manipulation techniques. Start with XOR cancellation in Single Number, work through bit counting and masking, and finish with the greedy bit construction in Maximum XOR. By the end, you should be able to spot when a problem can be solved with bit-level operations and reach for the right tool.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .