Bit Manipulation

A small pattern with outsized returns: most bit problems reduce to five memorized identities. If a problem says "without extra memory" or "appears exactly once/twice", think XOR before anything else.

The identities

Templates

# XOR fold — the element that appears once
def single(nums):
    acc = 0
    for x in nums: acc ^= x
    return acc

# Popcount via Kernighan: loops once per SET bit
def popcount(x):
    n = 0
    while x:
        x &= x - 1
        n += 1
    return n

# Add without '+': XOR = sum bits, AND<<1 = carries
def add(a, b):
    mask = 0xFFFFFFFF                   # simulate 32-bit in Python
    while b & mask:
        a, b = a ^ b, (a & b) << 1
    a &= mask if b > mask else 0xFFFFFFFFFFFFFFFF  # normalize
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)   # restore sign

Key variations

• XOR with expected values: missing number = XOR of 0..n and all elements — Missing Number.
• Appears once among triples: count bits mod 3 per position, or the two-variable automaton — Single Number II.
• DP on bits: bits[i] = bits[i >> 1] + (i & 1) — Counting Bits.
• Bit-by-bit reconstruction: reverse by shifting out of one number into another — Reverse Bits.
• XOR as difference detector: a ^ b has set bits exactly where they differ — Hamming Distance is popcount(a ^ b).

Classic problems

• Single Number — the XOR fold
• Single Number II — the tricky sibling
• Number of 1 Bits — Kernighan
• Counting Bits — bit DP
• Missing Number
• Reverse Bits
• Power of Two
• Sum of Two Integers — add without +

Pitfalls

• Python ints are unbounded — negative-number bit problems need explicit 32-bit masking (see add above); this will come up in Sum of Two Integers.
• >> on negatives is arithmetic shift in most languages (sign-extends); use unsigned/logical shift where available (>>> in Java/JS).
• Operator precedence: x & 1 == 0 parses as x & (1 == 0) — parenthesize bit expressions.
• Claiming O(1) space while building a list of bits — the trick is doing it with two integers.