How It Works

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.