Interview Patterns

March 2026 · 35 min read

This is the culmination of the series. Every classic bit manipulation interview problem, categorized by pattern, with full solutions and analysis.

Pattern 1: Single Pass XOR

Single Number (LC 136)

Problem: Every element appears twice except one. Find it.

int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int n : nums) result ^= n;
    return result;
}
// Time O(n), Space O(1). Covered in XOR Patterns.

CP note: O(n) time and O(1) space is the information-theoretic lower bound for this problem — you must read every element, and you cannot get below a constant number of words. No hash-set or sort-based solution can beat the XOR fold.

▶ Single Number Walk-through

Step through the XOR fold for [4, 1, 2, 1, 2] to see how duplicates cancel out.

Missing Number (LC 268)

int missingNumber(vector<int>& nums) {
    int n = nums.size(), result = n;
    for (int i = 0; i < n; ++i) result ^= i ^ nums[i];
    return result;
}

CP note: the Gauss-sum approach — n*(n+1)/2 - sum(nums) — is also O(n)/O(1), but it overflows when n is near $2^{16}$ in 32-bit, and earlier in fixed-width contest languages. The XOR form has no overflow whatsoever and is the safer default.

Pattern 2: Bit Counting / Popcount

Number of 1 Bits (LC 191)

int hammingWeight(uint32_t n) {
    int count = 0;
    while (n) { n &= n - 1; ++count; }
    return count;
}
// Kernighan's algorithm: O(k) where k = set bits

Counting Bits (LC 338)

vector<int> countBits(int n) {
    vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) dp[i] = dp[i & (i - 1)] + 1;
    return dp;
}
// O(n) total, O(1) per element using the clear-lowest-bit relation

Hamming Distance (LC 461)

int hammingDistance(int x, int y) {
    return __builtin_popcount(x ^ y);
}

Pattern 3: Power of Two / Single Bit

Power of Two (LC 231)

bool isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

Power of Four (LC 342)

bool isPowerOfFour(int n) {
    // Must be power of 2, AND the single set bit must be at an even position
    return n > 0 && (n & (n - 1)) == 0 && (n & 0x55555555);
    // 0x55555555 = 0b01010101... (bits at even positions)
}

Pattern 4: Bit Reversal / Manipulation

Reverse Bits (LC 190)

uint32_t reverseBits(uint32_t n) {
    n = ((n & 0x55555555) << 1)  | ((n >> 1) & 0x55555555);
    n = ((n & 0x33333333) << 2)  | ((n >> 2) & 0x33333333);
    n = ((n & 0x0F0F0F0F) << 4)  | ((n >> 4) & 0x0F0F0F0F);
    n = ((n & 0x00FF00FF) << 8)  | ((n >> 8) & 0x00FF00FF);
    n = (n << 16) | (n >> 16);
    return n;
}

Complement of Base 10 Integer (LC 1009)

int bitwiseComplement(int n) {
    if (n == 0) return 1;
    int mask = (1 << (32 - __builtin_clz(n))) - 1;
    return n ^ mask;
    // Create a mask with same bit-length as n, XOR to flip all bits
}

Pattern 5: Subset Enumeration

Subsets (LC 78)

vector<vector<int>> subsets(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> result;
    for (int mask = 0; mask < (1 << n); ++mask) {
        vector<int> subset;
        for (int i = 0; i < n; ++i) {
            if (mask & (1 << i)) subset.push_back(nums[i]);
        }
        result.push_back(subset);
    }
    return result;
}
// 2^n subsets, each built in O(n) → O(n × 2^n) total

CP note: the loop for (mask = 0; mask < (1<<n); ++mask) is the bridge to bitmask DP — the same enumeration generates every possible "subset state" in canonical order. Once you internalize this, problems like Beautiful Arrangement, Partition to K Equal Sum Subsets, and Shortest Superstring all look like decorated versions of this loop.

Pattern 6: Bit DP / State Compression

Can I Win (LC 464)

bool canIWin(int maxChoosable, int target) {
    if (maxChoosable * (maxChoosable + 1) / 2 < target) return false;
    unordered_map<int, bool> memo;

    function<bool(int, int)> dfs = [&](int mask, int total) -> bool {
        if (memo.count(mask)) return memo[mask];
        for (int i = 1; i <= maxChoosable; ++i) {
            if (mask & (1 << i)) continue;  // already used
            if (total + i >= target) return memo[mask] = true;
            if (!dfs(mask | (1 << i), total + i))
                return memo[mask] = true;  // opponent loses
        }
        return memo[mask] = false;
    };

    return dfs(0, 0);
}

Pattern 7: Miscellaneous Classics

Sum of Two Integers Without + (LC 371)

int getSum(int a, int b) {
    while (b != 0) {
        int carry = a & b;   // bits that produce carry
        a = a ^ b;           // sum without carry
        b = carry << 1;     // carry propagated
    }
    return a;
}
// Simulates half-adder logic: XOR = sum, AND = carry

UTF-8 Validation (LC 393)

bool validUtf8(vector<int>& data) {
    int remaining = 0;
    for (int byte : data) {
        byte &= 0xFF;  // only care about lowest 8 bits
        if (remaining == 0) {
            if ((byte >> 7) == 0b0)        remaining = 0;
            else if ((byte >> 5) == 0b110)  remaining = 1;
            else if ((byte >> 4) == 0b1110) remaining = 2;
            else if ((byte >> 3) == 0b11110) remaining = 3;
            else return false;
        } else {
            if ((byte >> 6) != 0b10) return false;
            --remaining;
        }
    }
    return remaining == 0;
}

Maximum XOR of Two Numbers (LC 421)

int findMaximumXOR(vector<int>& nums) {
    int maxXor = 0, mask = 0;
    for (int i = 31; i >= 0; --i) {
        mask |= (1 << i);
        unordered_set<int> prefixes;
        for (int n : nums) prefixes.insert(n & mask);

        int candidate = maxXor | (1 << i);
        for (int prefix : prefixes) {
            if (prefixes.count(prefix ^ candidate)) {
                maxXor = candidate;
                break;
            }
        }
    }
    return maxXor;
}
// Greedy bit-by-bit from MSB. Try to set each bit in the result.
// Uses the property: if a ^ b = c, then a ^ c = b.

Interview Study Plan

Day	Focus	Problems
1	XOR basics	Single Number (136), Missing Number (268), Hamming Distance (461)
2	Bit counting	Number of 1 Bits (191), Counting Bits (338), Power of Two (231)
3	Manipulation	Reverse Bits (190), Sum Without + (371), Single Number II (137)
4	Subsets	Subsets (78), Single Number III (260), Maximum XOR (421)
5	Advanced	Can I Win (464), UTF-8 Validation (393), Power of Four (342)

Summary

XOR cancellation solves "find the unique" problems in O(n) time, O(1) space.
Kernighan's algorithm counts bits in O(k) time.
Power of 2 = single bit set = n & (n-1) == 0.
Subset enumeration via bitmasks: iterate 0 to 2^n - 1.
Bitmask DP compresses subset state into a single integer.
Addition without + uses XOR (sum) and AND + shift (carry).
Master the 15 problems in the study plan and you will handle any bit manipulation interview question.

Practice Problems

The high-frequency interview set. If you can solve all ten in under 25 minutes each, your bit fluency is solid.

LC 136 — Single Number easy XOR fold.
LC 137 — Single Number II medium bit-by-bit mod-3 counter or two-state automaton.
LC 260 — Single Number III medium XOR all, then split on lowest set bit.
LC 268 — Missing Number easy XOR with indices.
LC 191 — Number of 1 Bits easy Kernighan loop.
LC 338 — Counting Bits easy DP dp[i] = dp[i & (i-1)] + 1.
LC 78 — Subsets medium bitmask enumeration.
LC 461 — Hamming Distance easy popcount(x ^ y).
LC 477 — Total Hamming Distance medium contribute by bit position: cnt * (n - cnt).
LC 318 — Maximum Product of Word Lengths medium 26-bit char masks; pair with (a & b) == 0.
LC 421 — Maximum XOR of Two Numbers medium greedy MSB-first hashset, or trie.
SPOJ — Shuffling medium XOR-based parity/permutation tracking.