Bit Manipulation

A number is a row of switches

Everything in this pattern comes from one shift in perspective: stop reading 12 as a quantity and start reading it as 1100 — four columns, each either on or off. Bitwise operators work on every column at once, independently, in a single CPU instruction. That is why these solutions come out O(1) extra space with no hash set in sight.

XORThe four facts worth memorising

• x ^ x == 0 — anything cancels itself. This is the entire Single Number family.
• x ^ 0 == x — zero is the identity, so it is always the safe starting accumulator.
• x ^ y ^ y == x — XOR is its own inverse; applying it twice undoes it.
• XOR is commutative and associative, so the order of a whole array of XORs never matters.

Put those together and "one number appears once, the rest appear twice" stops being a counting problem. Fold the array into a single accumulator and the duplicates delete each other on the way past.

Five moves that cover almost every problem

M1n & (n - 1) — clear the lowest set bit

Subtracting 1 borrows through the trailing zeros: the lowest 1 turns into a 0 and every 0 below it turns into a 1, while everything above is left alone. ANDing the two therefore keeps the untouched top and wipes the tail — exactly one set bit disappears.

Two consequences you will use constantly: looping n = n & (n - 1) until n is zero counts the set bits in O(number of 1s) instead of O(32), and a number with exactly one set bit satisfies n & (n - 1) == 0 — the power-of-two test.

Two's complement, and the gotcha that breaks LC 371

Hardware stores a negative number as its two's complement: flip every bit, then add 1. In 8 bits, 5 is 00000101, so -5 is 11111011. The top bit doubles as the sign, and the beauty of the scheme is that ordinary binary addition then "just works" for negatives with no special cases.

Python agrees with all of that in spirit — ~x == -x - 1, and (-5 >> i) & 1 gives you the right two's-complement bit — but with one enormous difference:

That is the whole difficulty of LC 371 (Sum of Two Integers). The carry-propagation loop below is correct C; in Python, a negative operand keeps generating a carry that marches up forever and the while loop never ends. The fix is to & 0xFFFFFFFF after every step, which simulates a 32-bit register, and then translate the result back into a signed Python int at the very end.

When to reach for bits

• The statement says "without using extra memory" or "in O(1) space" — usually a XOR-cancellation problem.
• The words binary, bit, power of two, complement, mask, parity appear literally.
• Elements appear a fixed number of times and one is the odd one out (LC 136 / 137 / 260).
• You need every subset of a set with n ≤ 20 — mask 0 .. 2n-1 enumerates them, and each mask doubles as a DP state (bitmask DP).
• You are tracking a small set of flags (26 lowercase letters, visited cities) and a hash set feels heavy — pack them into one integer.
• Two things need comparing column by column: Hamming distance, Gray code, common prefixes.

The four templates to memorize

T1XOR fold — cancel the pairs

def single_number(nums):
    running_xor = 0                 # x ^ 0 == x, so 0 is the safe start
    for num in nums:
        # Every value that appears twice cancels itself out (x ^ x == 0),
        # so after the whole pass only the loner is left standing.
        running_xor = running_xor ^ num
    return running_xor

The same fold solves LC 268 (Missing Number) — XOR all the indices and all the values together, and everything pairs off except the number that was never there:

def missing_number(nums):
    # Indices run 0..n-1 but the values are drawn from 0..n, so seed the
    # accumulator with n — the one index that has no slot of its own.
    missing = len(nums)
    for index, num in enumerate(nums):
        missing = missing ^ index ^ num
    return missing

T2Brian Kernighan — one loop per set bit

def count_set_bits(n):
    count = 0
    while n != 0:
        # Erase the lowest 1. The loop therefore runs exactly
        # once per set bit, not once per column.
        n = n & (n - 1)
        count += 1
    return count


def is_power_of_two(n):
    # A power of two has exactly one set bit, so a single erase empties it.
    # The n > 0 guard matters: 0 & -1 == 0 would sneak through otherwise.
    return n > 0 and (n & (n - 1)) == 0

In a real interview bin(n).count("1") or n.bit_count() (Python 3.10+) is the honest one-liner — write the loop only when asked to show the mechanism.

T3Fixed-width bit walk

def reverse_bits(n):
    result = 0
    # Exactly 32 iterations — the width is part of the problem statement,
    # and Python will not stop the loop for us the way a register would.
    for _ in range(32):
        lowest_bit = n & 1          # read the bit about to fall off n
        result = (result << 1) | lowest_bit   # push it onto result
        n = n >> 1
    return result

The shape — pull the low bit off one number, push it onto another — is the same one used for binary conversion, parity and Gray code.

T4Bitmask enumeration — every subset

def subsets(nums):
    n = len(nums)
    all_subsets = []

    # There are 2**n subsets and 2**n masks of n bits. Line them up:
    # mask 0b101 with nums = [1, 2, 3] means "take nums[0] and nums[2]".
    for mask in range(1 << n):
        current = []
        for index in range(n):
            if mask & (1 << index):     # is column "index" on in this mask?
                current.append(nums[index])
        all_subsets.append(current)

    return all_subsets

Same idea powers bitmask DP: the mask becomes the state ("which cities have I visited"), and dp[mask] is indexed by an integer instead of a frozenset.

Three problems that bend the basic tricks

LC 338Counting Bits — DP on the shift

Counting each number from scratch is O(n log n). Instead notice that value and value >> 1 have the same bits except for the one that got shifted off — and we already computed the answer for the smaller number.

def count_bits(n):
    bits = [0] * (n + 1)
    for value in range(1, n + 1):
        half = value >> 1           # value with its last bit chopped off
        last_bit = value & 1        # the bit we chopped: 0 or 1
        bits[value] = bits[half] + last_bit
    return bits

LC 137Single Number II — count columns mod 3

Every value appears three times except one. XOR is useless here, so drop to the column level: if a bit is set in a tripled value it contributes 3 to that column's tally, so any column whose tally is not a multiple of 3 belongs to the loner. There is a famous two-variable "ones / twos" version — this one is the one you can explain.

def single_number_ii(nums):
    result = 0

    for bit_position in range(32):
        ones_in_column = 0
        for num in nums:
            # For negatives Python still reports the correct
            # two's-complement bit here, which is what we want.
            if (num >> bit_position) & 1:
                ones_in_column += 1

        # The tripled values contribute 0 or 3; the leftover is the loner's bit.
        if ones_in_column % 3 != 0:
            result = result | (1 << bit_position)

    # Bit 31 set means the 32-bit pattern is negative — Python would
    # otherwise hand back a large positive number.
    if result >= (1 << 31):
        result -= (1 << 32)
    return result

LC 260Single Number III — split into two buckets

Two loners, everything else paired. XORing everything gives first ^ second — not an answer, but every set bit in it is a column where the two loners differ. Pick any one of those columns and it partitions the array into two halves, each containing exactly one loner. Then T1 twice.

def single_number_iii(nums):
    xor_of_both = 0
    for num in nums:
        xor_of_both = xor_of_both ^ num      # pairs vanish; first ^ second remains

    # Isolate one column where the two loners disagree (M2).
    splitting_bit = xor_of_both & -xor_of_both

    first = 0
    second = 0
    for num in nums:
        # Duplicates always land in the same bucket as each other,
        # so they still cancel inside their own bucket.
        if num & splitting_bit:
            first = first ^ num
        else:
            second = second ^ num

    return [first, second]

Where bit code goes wrong

# WRONG: parses as  n & (1 + 1)  ->  n & 2
if n & 1 + 1:
    ...

# WRONG: parses as  x & (mask == 0). For any non-zero mask that is
# x & False, i.e. 0 -- so the branch never runs.
if x & mask == 0:
    ...

# RIGHT: say exactly what you mean
if (x & mask) == 0:
    ...