Bit Manipulation

Bit operations let you encode state compactly and exploit binary properties. The invariant is to track exactly which bits represent what and avoid sign confusion.

Pattern A: Bit-wise addition

Use when: you add binary strings or need manual carry.

Invariant: carry is the only state between bit positions.

Skeleton:

i = len(a)-1; j = len(b)-1; carry = 0
while i >= 0 or j >= 0 or carry > 0:
    sum = carry
    if i >= 0: sum += a[i]-'0'; i--
    if j >= 0: sum += b[j]-'0'; j--
    carry = sum / 2
    out.append(sum % 2)
reverse out

Problems:

• add-binary.

Pattern B: Fixed-width bit reversal

Use when: you must reverse bits in a 32-bit integer.

Invariant: each step moves the current LSB to the result.

Skeleton:

res = 0
for i in 0..31:
    res = (res << 1) | (n & 1)
    n >>= 1
return res

Problems:

• reverse-bits.

Pattern C: Counting set bits

Use when: you need the number of 1s in a word.

Invariant: n & (n-1) clears the lowest set bit.

Skeleton:

count = 0
while n != 0:
    n &= (n-1)
    count++

Problems:

• number-of-1-bits.

Pattern D: XOR for unique elements

Use when: every element appears twice except one.

Invariant: x ^ x = 0 and x ^ 0 = x.

Skeleton:

ans = 0
for x in nums: ans ^= x
return ans

Problems:

• single-number.

Pattern E: Bit counts mod k

Use when: every element appears k times except one.

Invariant: for each bit, count % k gives the unique element's bit.

Skeleton:

counts[32] = 0
for x in nums:
    for b in 0..31:
        if (x >> b) & 1: counts[b]++
ans = 0
for b in 0..31:
    if counts[b] % 3 != 0: ans |= (1 << b)

Problems:

• single-number-ii.

Pattern F: Range AND by common prefix

Use when: you AND all numbers in [m, n].

Invariant: differing low bits vanish; only the common prefix survives.

Skeleton:

shift = 0
while m != n:
    m >>= 1
    n >>= 1
    shift++
return m << shift

Problems:

• bitwise-and-of-numbers-range.

When to use Bit Manipulation (checklist)

• The problem mentions bits, parity, or powers of two.
• You can encode state or count occurrences per bit.

Common failures (checklist)

• Mixing signed and unsigned shifts.
• Forgetting fixed width (32-bit) constraints.
• Not handling negative values in bit count reconstructions.

Problem mapping

• add-binary: bit-wise addition with carry.
• reverse-bits: fixed-width reversal.
• number-of-1-bits: n & (n-1) loop.
• single-number: XOR fold.
• single-number-ii: bit counts mod 3.
• bitwise-and-of-numbers-range: shift to common prefix.