How It Works

This chapter traces small examples by hand to show why the classic tricks work: the lowest set bit x & -x, clearing it with x & (x - 1), popcount, subset enumeration with bitmasks, submask enumeration, a first look at bitmask DP, and XOR tricks.

x & -x: the lowest set bit

Take x = 12, or 00001100 in 8 bits. Since -x is ~x + 1:

In ~x, every bit below the lowest set bit of x becomes 1. Adding 1 carries through them and stops exactly at that position. So x and -x share that one bit, disagree on everything above it, and are both 0 below it; the AND keeps only that bit. A Fenwick tree uses this to jump between ranges.

x & (x - 1): clearing the lowest set bit

Subtracting 1 turns the lowest set bit into 0 and every bit below it into 1. For 12 = 1100, 11 = 1011, and the AND is 1000 = 8. Two tools follow at once:

• Power-of-two test: x > 0 and (x & (x - 1)) == 0
• Counting set bits (Brian Kernighan's method): the number of clears until x reaches 0 is the popcount.

Tracing popcount for x = 13 (1101):

The loop runs once per set bit, so sparse numbers finish quickly.

def popcount(x: int) -> int:
    count = 0
    while x:
        x &= x - 1
        count += 1
    return count

print(popcount(13), popcount(255), (13).bit_count())  # 3 8 3

Enumerating subsets with a bitmask

A set of n items such as ["a", "b", "c"] has 2^n = 8 subsets, one for each integer from 0 to 7. If bit i of the mask is 1, item i is in the subset.

items = ["a", "b", "c"]
n = len(items)
for mask in range(1 << n):
    chosen = [items[i] for i in range(n) if (mask >> i) & 1]
    print(format(mask, "03b"), chosen)

Set algebra becomes integer arithmetic: union is OR, intersection is &, difference is a & ~b, membership is (a >> i) & 1.

Enumerating submasks

To visit only the subsets of a given mask, repeat sub = (sub - 1) & mask. For mask = 1011 the walk is 1011, 1010, 1001, 1000, 0011, 0010, 0001, then 0. Subtracting 1 turns the low bits on and the AND removes anything outside the mask, so each step moves to the next smaller number made only of the mask's bits.

mask = 0b1011
sub = mask
while True:
    print(format(sub, "04b"))
    if sub == 0:
        break
    sub = (sub - 1) & mask

A first look at bitmask DP

When a DP state contains "the set of items used so far", encode that set as an integer and use it as an array index. To assign n jobs to n workers at minimum total cost, let dp[mask] be the cheapest way to give the jobs in mask to the first popcount(mask) workers. The next worker is determined by popcount(mask), so there are only 2^n states, each trying at most n jobs: O(2^n * n) overall. The practice chapter builds a full example.

XOR tricks

XOR satisfies a ^ a == 0 and a ^ 0 == a, and it is commutative and associative. XOR together a list where every value appears twice except one, and the pairs cancel: 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4.

from functools import reduce

print(reduce(lambda a, b: a ^ b, [4, 1, 2, 1, 2]))   # 4
a, b = 0b1100, 0b1010
print(bin(a ^ b), (a ^ b).bit_count())              # 0b110 2: Hamming distance

Summary

x & -x isolates the lowest set bit and x & (x - 1) removes it. The integers 0 to 2^n - 1 are exactly the subsets of n items, and (sub - 1) & mask walks down through submasks. These few moves are the foundation of bitmask DP and XOR puzzles.