Bit Manipulation Interview Questions: 5 Core Patterns

Bit manipulation problems look intimidating, but they all reduce to the same 5 patterns. Once you recognize which pattern a problem belongs to, the solution is nearly mechanical. Master these patterns and you'll handle any bit manipulation question in a FAANG interview.

When to Use Bit Manipulation

Bit manipulation is the right approach when:

• The problem involves finding a unique element among duplicates
• You need to check/set/clear/toggle specific bits
• The problem asks for all subsets or all combinations of a set
• The input is integers and the problem asks about parity, powers of 2, or binary representation
• You see keywords like "XOR," "bit," "binary," "power of two," or "single number"

The 5 core patterns: XOR cancellation, bit counting, masking, subset enumeration, and binary construction.

Pattern 1: XOR Cancellation

XOR has three properties that make it powerful:

• a ^ a = 0 (any number XORed with itself is zero)
• a ^ 0 = a (anything XORed with zero is itself)
• XOR is commutative and associative (order doesn't matter)

This means if you XOR all elements where every element appears twice except one, the duplicates cancel out and you're left with the unique element.

Example: Single Number

def single_number(nums):
    result = 0
    for num in nums:
        result ^= num
    return result

Walkthrough with [4,1,2,1,2]:

1. 0 ^ 4 = 4
2. 4 ^ 1 = 5
3. 5 ^ 2 = 7
4. 7 ^ 1 = 6
5. 6 ^ 2 = 4
6. Result: 4 (the unique element)

Time: O(n). Space: O(1).

Extended: Two Unique Numbers

When exactly two numbers appear once and all others appear twice:

def single_number_two(nums):
    xor_all = 0
    for num in nums:
        xor_all ^= num

    rightmost_bit = xor_all & (-xor_all)
    a = 0
    for num in nums:
        if num & rightmost_bit:
            a ^= num
    return [a, xor_all ^ a]

The rightmost set bit splits all numbers into two groups. XOR each group separately to isolate the two unique numbers.

Pattern 2: Bit Counting

Counting set bits (1s in binary) appears in problems about Hamming weight, parity, and population count. Python's bin(x).count('1') works but is slow. The optimal approach uses Brian Kernighan's trick: x & (x - 1) clears the lowest set bit.

Example: Counting Bits

def count_bits(n):
    result = [0] * (n + 1)
    for i in range(1, n + 1):
        result[i] = result[i >> 1] + (i & 1)
    return result

Walkthrough for n = 5:

Time: O(n). Space: O(n).

Brian Kernighan's Trick

def count_ones(x):
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

Each iteration clears one set bit, so it runs in O(number of set bits) time — faster than checking all 32 bits.

Pattern 3: Masking (Check/Set/Clear/Toggle Bits)

Bitmasks let you manipulate individual bits using & (AND), | (OR), ^ (XOR), and ~ (NOT). Use masking when you need to track which elements have been seen or toggle specific flags.

Example: Find Missing Number Using Mask

def find_missing(nums, n):
    xor_all = 0
    for i in range(n + 1):
        xor_all ^= i
    for num in nums:
        xor_all ^= num
    return xor_all

This works because XORing 0..n and then XORing all elements cancels every number that appears, leaving only the missing one.

Example: Check if Power of Two

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0

Powers of two have exactly one set bit. n & (n - 1) clears that bit, so the result is 0 if and only if n is a power of two.

Time: O(1). Space: O(1).

Pattern 4: Subset Enumeration

Generate all subsets of a set using bitmasks. For a set of size n, there are 2^n subsets. Each subset maps to a number from 0 to 2^n - 1 where each bit indicates whether the corresponding element is included.

Example: All Subsets

def subsets(nums):
    n = len(nums)
    result = []
    for mask in range(1 << n):
        subset = []
        for i in range(n):
            if mask & (1 << i):
                subset.append(nums[i])
        result.append(subset)
    return result

Walkthrough with [1,2,3]:

Time: O(n × 2^n). Space: O(n × 2^n).

When to Use This Over Backtracking

Use bitmask subset enumeration when:

• n ≤ 20 (2^20 = ~1M, which is fine)
• You need all subsets, not just those meeting a constraint
• You want simpler code than recursive backtracking

For n > 20, backtracking with pruning is more practical.

Pattern 5: Binary Construction (Build Numbers from Bits)

Some problems ask you to construct integers bit by bit, often from most significant to least significant. This is common in problems about binary representation, bit streams, or encoding.

Example: Add Binary Strings

def add_binary(a, b):
    result = []
    carry = 0
    i, j = len(a) - 1, len(b) - 1

    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0:
            total += int(a[i])
            i -= 1
        if j >= 0:
            total += int(b[j])
            j -= 1
        result.append(str(total % 2))
        carry = total // 2

    return ''.join(reversed(result))

Walkthrough with a = "11", b = "1":

1. i=1, j=0: total = 0 + 1 + 1 = 2 → append "0", carry = 1
2. i=0, j=-1: total = 1 + 1 + 0 = 2 → append "0", carry = 1
3. i=-1, j=-1, carry=1: total = 1 → append "1", carry = 0
4. Result: "100"

Time: O(max(len(a), len(b))). Space: O(max(len(a), len(b))).

Complexity Summary

Common Mistakes

1. Using >> instead of // for negative numbers. In Python, >> is arithmetic shift (sign-extends), which behaves differently from // for negative numbers. For bit manipulation on positive integers, they're equivalent.

2. Forgetting that XOR is commutative. Many candidates try to maintain order during XOR operations. You don't need to — the order of XOR operations doesn't matter.

3. Off-by-one in subset enumeration. Use range(1 << n) to include all subsets from empty to full. Starting at 1 skips the empty set.

4. Using n & (n - 1) to check power of two without handling n ≤ 0. 0 & (-1) in two's complement doesn't behave as expected. Always check n > 0 first.

5. Confusing left shift << with right shift >>. 1 << k creates a mask with bit k set. x >> k shifts bits right (divides by 2^k). Mixing these up silently produces wrong answers.

Practice Problems

These problems cover all 5 bit manipulation patterns. Solve them in order to build your pattern recognition.

1. Single Number — XOR cancellation. Find the element that appears once when every other appears twice.

2. Counting Bits — Bit counting with DP. Count set bits for all numbers from 0 to n.

3. Power of Two — Masking trick. Check if a number is a power of two using n & (n - 1).

4. Subsets — Subset enumeration. Generate all subsets of a given set of distinct integers.

5. Add Binary — Binary construction. Add two binary strings and return the result.

Practice These Patterns With Alex

Bit manipulation problems are about recognizing which pattern applies and executing it cleanly. The hardest part isn't the bit operations — it's explaining why your approach works under interview pressure. Practice with an AI interviewer who asks follow-up questions about your bit manipulation choices.

Start a mock coding interview →

Frequently Asked Questions