Home / Blog / Bit Manipulation Interview Pattern Chooser

Bit Manipulation Interview Pattern Chooser

Published 2026-10-14 · Luna Interview

Bit manipulation problems scare a lot of candidates because they feel like tricks you either know or don't. In practice, most interview questions in this area reduce to a handful of reusable moves. This bit manipulation interview pattern chooser helps you recognize which move fits, write it cleanly, and explain it so the interviewer follows along.

The 10-second classification

Ask yourself:

1. Do pairs cancel out, or is one element "the odd one"? → XOR
2. Do you need to test, set, or clear a specific bit? → masks and shifts
3. Are you counting set bits or checking powers of two? → n & (n - 1) tricks
4. Is the input tiny (n ≤ 20) and you need all subsets or states? → bitmask enumeration / bitmask DP
5. Do you need to represent a small set compactly (letters, visited nodes)? → integer as a set

A useful sentence:

"This looks like a pairing problem, so XOR should cancel the duplicates and leave the unique value in O(n) time and O(1) space."

Core operations reference

Memorize this table. Most problems combine two or three of these.

Pattern 1: XOR cancellation

Signals: "every element appears twice except one," "find the missing number," "swap without a temp."

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

Why it works: a ^ a = 0 and a ^ 0 = a, and XOR is commutative and associative, so order doesn't matter.

Variant—missing number in 0..n: XOR all indices and all values; the leftover is the missing one.

Variant—two unique numbers: XOR everything to get a ^ b, isolate any set bit with diff & -diff, then split the numbers into two groups by that bit and XOR each group.

Pattern 2: counting bits

Signals: "number of 1 bits," "Hamming distance," "count bits for every number up to n."

def count_bits(x):
    count = 0
    while x:
        x &= x - 1   # drop lowest set bit
        count += 1
    return count

This runs in O(number of set bits), not O(32). Say that—it's a nice detail.

For "counts for all numbers 0..n," use DP: bits[i] = bits[i >> 1] + (i & 1).

Hamming distance between a and b is just count_bits(a ^ b).

Pattern 3: integer as a small set

Signals: characters from a fixed alphabet, "no shared letters," visited nodes in a small graph.

def mask_of(word):
    m = 0
    for ch in word:
        m |= 1 << (ord(ch) - ord('a'))
    return m

Two words share no letters if mask_of(a) & mask_of(b) == 0. That turns a set intersection into one O(1) operation.

Pattern 4: subset enumeration and bitmask DP

Signals: n ≤ 20, "all subsets," "visit every node once," assignment problems.

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

For bitmask DP (like a small traveling-salesman variant), the state is dp[mask][last]: the best cost having visited the set mask and ending at last. Complexity is O(2ⁿ · n²), which is why the constraint is tiny.

Say it: "n is at most 16, which hints at 2ⁿ states. I'll use a bitmask to represent the visited set."

Decision table

Language gotchas

• Python: integers are arbitrary precision, so ~x is -x - 1 and negative numbers don't wrap at 32 bits. Mask with & 0xFFFFFFFF when the problem assumes 32-bit behavior.
• Java: use >>> for an unsigned right shift; >> preserves the sign.
• JavaScript: bitwise operators work on 32-bit signed integers; use >>> 0 to get unsigned.
• C++: shifting by ≥ the type's width is undefined behavior; use 1LL << i for wide masks.

Mention the relevant one—it shows you know where bugs hide.

Common mistakes

1. Operator precedence: in many languages x & 1 == 0 parses as x & (1 == 0). Use parentheses.
2. Forgetting negative numbers in Python
3. Using bitmask DP when n is 40 (2⁴⁰ is far too large)
4. Explaining nothing—bit tricks look like magic unless you narrate the invariant

Soft practice note

Bit problems get easier once the core table is automatic and you can explain each trick in one sentence. If you want a calm, structured way to rehearse that narration with a timer, Luna Interview is built for practice and prep—before the interview, not as a shortcut during one.

Quick checklist

• [ ] Operations table memorized
• [ ] XOR fold and two-unique split practiced
• [ ] x & (x - 1) loop explained aloud
• [ ] Bitmask set and subset enumeration written from memory
• [ ] Language-specific shift and sign rules reviewed
• [ ] Parentheses around every bitwise comparison

Bit manipulation isn't about memorizing tricks. It's about recognizing which of five moves the problem is asking for.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.