Bit Manipulation Tricks Explained — XOR Patterns, Subset Enumeration, Bitmask DP [LC 136, Google, Meta]

Algorithm Statement#

A toolbox of constant-time bit operations and the patterns they unlock:

1. XOR identities: $a \oplus a = 0$, $a \oplus 0 = a$, commutative and associative.
2. Lowest set bit: n & -n isolates it; n & (n - 1) clears it.
3. Population count: Brian Kernighan's algorithm — repeatedly clear the lowest set bit.
4. Subset enumeration: iterate for sub = mask; sub > 0; sub = (sub - 1) & mask to walk all submasks.
5. Bitmask DP: state = bitmask, transition = flip / set / clear bits.

Constraints typical:

• $1 \le n \le 20$ for bitmask DP (so $2^n \le 10^6$).
• $1 \le n \le 10^{18}$ for raw bit tricks.

Examples:

LC 136 Single Number:  XOR all elements → answer
LC 191 Number of 1 Bits: popcount(n)
LC 78 Subsets:           iterate masks 0..(1<<n)-1
LC 1125 Smallest Sufficient Team: bitmask DP

Why This Problem Matters#

Bit manipulation appears in every interview rubric, often as a "warm-up" problem that secretly tests whether you have internalised binary representation. Google asks LC 136 in 30 percent of phone screens. Meta uses bitmask DP in onsites for travelling-salesman style problems. Stripe uses XOR in idempotency-key dedup tricks. The candidates who solve it elegantly stand out instantly — those who reach for hash sets and sorting on a single-number problem look juniorish.

Beyond interviews, bitmask DP is the standard technique for problems where the subset of selected items matters but $n \le 20$. With that constraint, $2^n$ states fit and you can sweep them in $O(2^n \cdot n)$.

The Core Insight#

XOR is addition modulo 2 on each bit. Three identities flow from that:

• $a \oplus a = 0$ (every bit cancels itself).
• $a \oplus 0 = a$ (zero is the identity).
• XOR is commutative and associative, so order does not matter when XOR-ing a sequence.

These three lines solve LC 136 (single number among pairs) in $O(n)$ time and $O(1)$ space.

$n \mathbin{\&} (n - 1)$ clears the lowest set bit. Subtracting 1 flips the lowest set bit to 0 and turns all lower 0s to 1s. ANDing with $n$ wipes that bit and the carry chain. Useful for popcount and power-of-two checks: $n$ is a power of two iff $n > 0$ and $n \mathbin{\&} (n - 1) = 0$.

$n \mathbin{\&} -n$ isolates the lowest set bit. Two's complement makes $-n$ equal to $\sim n + 1$, which has the lowest set bit of $n$ followed by zeros below.

Submask enumeration. Given a mask, enumerate all submasks (subsets):

sub = mask
while sub > 0:
    process(sub)
    sub = (sub - 1) & mask

This visits each submask exactly once. Total work over all masks is $O(3^n)$ because each pair (mask, submask) corresponds to a 3-way assignment per bit (0, 1 in mask, 1 in submask).

Bitmask DP. Let dp[mask] represent some optimum over subsets indicated by mask. Transitions usually look like dp[mask | (1 << i)] = best(dp[mask | ...], dp[mask] + cost) for some addition rule. Travelling-salesman is the canonical example: dp[mask][i] = min cost ending at city i having visited mask.

Visual Dry Run#

LC 136 (single number) on nums = [4, 1, 2, 1, 2].

xor = 0
xor ^= 4  → 4   (binary 100)
xor ^= 1  → 5   (binary 101)
xor ^= 2  → 7   (binary 111)
xor ^= 1  → 6   (binary 110)
xor ^= 2  → 4   (binary 100)
 
Result: 4. The pairs cancel, only the singleton remains.

Submask enumeration over mask = 1011 (11 in decimal):

sub = 1011 → process
sub = (1011 - 1) & 1011 = 1010 & 1011 = 1010 → process
sub = 1010 - 1 = 1001, & 1011 = 1001 → process
sub = 1001 - 1 = 1000, & 1011 = 1000 → process
sub = 1000 - 1 = 0111, & 1011 = 0011 → process
sub = 0011 - 1 = 0010, & 1011 = 0010 → process
sub = 0010 - 1 = 0001, & 1011 = 0001 → process
sub = 0001 - 1 = 0000, & 1011 = 0000 → stop
 
8 submasks (= 2^3, the number of bits set in 1011).

Solution (Optimal)#

Python — Core Tricks#

# 1. XOR everything (LC 136)
def single_number(nums: list[int]) -> int:
    result = 0
    for x in nums:
        result ^= x
    return result
 
# 2. Population count (Brian Kernighan)
def popcount(n: int) -> int:
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
 
# 3. Power of two
def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0
 
# 4. Iterate all subsets of {0..n-1}
def all_subsets(n: int):
    for mask in range(1 << n):
        yield [i for i in range(n) if mask & (1 << i)]
 
# 5. Iterate submasks of a mask (LC 1125 style)
def submasks(mask: int):
    sub = mask
    while sub > 0:
        yield sub
        sub = (sub - 1) & mask
    yield 0

Complexity: XOR sweep $O(n)$. Popcount $O(\text{popcount}(n))$ — at most 64 iterations. Submask enumeration over all masks is $O(3^n)$.

Python — Bitmask DP (Travelling Salesman)#

def tsp(dist: list[list[int]]) -> int:
    n = len(dist)
    INF = float('inf')
    dp = [[INF] * n for _ in range(1 << n)]
    dp[1][0] = 0  # start at city 0
    for mask in range(1, 1 << n):
        for u in range(n):
            if not (mask & (1 << u)) or dp[mask][u] == INF:
                continue
            for v in range(n):
                if mask & (1 << v):
                    continue
                new_mask = mask | (1 << v)
                if dp[mask][u] + dist[u][v] < dp[new_mask][v]:
                    dp[new_mask][v] = dp[mask][u] + dist[u][v]
    full = (1 << n) - 1
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

Complexity: $O(n^2 \cdot 2^n)$ time, $O(n \cdot 2^n)$ memory.

JavaScript — Core Tricks#

const singleNumber = nums => nums.reduce((a, b) => a ^ b, 0);
 
const popcount = n => {
    let count = 0;
    while (n) { n &= n - 1; count++; }
    return count;
};
 
const isPowerOfTwo = n => n > 0 && (n & (n - 1)) === 0;
 
function* submasks(mask) {
    for (let sub = mask; sub > 0; sub = (sub - 1) & mask) yield sub;
    yield 0;
}

Common Mistakes#

1. Using n % 2 for parity in hot loops. n & 1 is faster and clearer. Most compilers optimise it the same, but signal intent in code.
2. Off-by-one in 1 << n. 1 << 31 overflows a 32-bit signed int. Use 1n << 31n (BigInt) in JavaScript or 1L << 31 (long) in Java.
3. XOR for "find duplicate". XOR works only when all elements except one appear an even number of times. With three duplicates, XOR mixes them.
4. Submask iteration starting condition. The loop body must run for sub = mask first, then decrement. Starting at sub = mask - 1 skips the full subset.
5. Bitmask DP exceeding 32 bits. With $n \ge 32$, you cannot use a single int. Use BigInt or a tuple of two 32-bit halves.
6. JavaScript bitwise on numbers above 2^{31}. JS coerces to 32-bit signed for & | ^, so working with 53-bit integers requires BigInt operators.

Interview Tips#

• Mention the XOR identity proof as soon as you spot LC 136. It is a 30-second solve and shows mathematical maturity.
• For popcount on a 64-bit integer, ask if hardware popcount (__builtin_popcountll) is available — it is $O(1)$ on x86 with SSE4.
• Bitmask DP triggers when $n \le 20$ and the problem says "subset". Always check the bound before reaching for it.
• For "find two single numbers among pairs", XOR everything, isolate any set bit, then partition by that bit and XOR each half.

Follow-up Questions#

Q1: Find the two non-duplicated numbers in an array where all others appear twice. A: XOR everything to get $a \oplus b$. Pick any set bit. Partition the array by that bit and XOR each partition.

Q2: Count set bits in numbers 0 through n. A: Use the recurrence $\text{bits}(i) = \text{bits}(i \mathbin{>>} 1) + (i \mathbin{\&} 1)$, $O(n)$ total.

Q3: Rotate the bits of a 32-bit number left by $k$. A: (n << k) | (n >>> (32 - k)) masked to 32 bits.

Q4: Solve LC 1125 Smallest Sufficient Team. A: Bitmask DP over the set of skills, $O(\text{people} \cdot 2^{\text{skills}})$.

Key Takeaways#

• XOR cancels pairs, isolating singletons in $O(n)$ time and $O(1)$ space — the canonical LC 136 solve.
• n & (n - 1) clears the lowest set bit; n & -n isolates it. Both are constant-time tricks behind popcount and power-of-two checks.
• Submask enumeration runs all subsets of a mask in $O(2^{\text{popcount}})$ via sub = (sub - 1) & mask.
• Bitmask DP turns subset-DP into $O(2^n \cdot n)$ — feasible only for $n \le 20$.
• Watch for language-specific bit-width pitfalls: JavaScript bitwise truncates to 32 bits unless you use BigInt; Java needs long for 64-bit masks.
• The XOR-and-isolate-bit pattern generalises to "find $k$ singletons among pairs" for $k$ up to a few — it is the bit-trick equivalent of dual-pointer.