Bit Manipulation and State Compression
Subsets as integers: enumerating \(2^n\) states, popcount and lowbit tricks, subset-sum DP, and the \(O(2^n n^2)\) travelling-salesman DP.
Leads to: 19.10 uses masks in meet-in-the-middle; 19.14 tells you when \(2^n\) is affordable. The Euler Lab’s Dynamic Programming and Combinatorics paths both hide bitmask problems.
Learning Objectives
Click a status chip to cycle: Not started → In progress → Studied → Practiced → Needs review → Mastered.
- Represent a subset of an \(n\)-element universe as an \(n\)-bit integer and translate set operations into bit operations.
- Enumerate all subsets, and all subsets of a given mask, in the right complexity (\(2^n\) and \(3^n\) respectively).
- Use popcount, lowbit (\(x\ \&\ {-x}\)), and mask arithmetic to write branch-free inner loops.
- Implement a bitmask DP (subset-sum reachability and the Held–Karp TSP) and state its exact complexity.
- Judge when \(2^n\) state compression is feasible and when it is not.
Key Vocabulary
- Bitmask
- An integer whose \(i\)-th bit records membership of element \(i\). Union = OR, intersection = AND, symmetric difference = XOR, complement = XOR with the full mask.
- Popcount
- The number of set bits. Python: bin(x).count('1') or x.bit_count() (3.10+).
- Lowbit
- \(x\ \&\ (-x)\) isolates the lowest set bit - the standard way to iterate over the elements of a mask in \(O(\text{popcount})\).
- Submask enumeration
- s = (s-1) & mask walks all submasks of mask in decreasing order; over all masks this totals \(3^n\) steps, not \(4^n\).
- Held–Karp
- The bitmask DP for TSP: state \((\text{visited set},\ \text{current city})\), cost \(O(2^n n^2)\) time and \(O(2^n n)\) memory.
- State compression
- Encoding an exponential-but-small state (a subset, a profile of a grid row) as an integer so it can index a DP array.
Intuition & Motivation
Sets as integers
| Set operation | Bit operation | Note |
|---|---|---|
| Is \(i\in S\)? | (S >> i) & 1 | 1 if present |
| Add \(i\) | S | (1 << i) | idempotent |
| Remove \(i\) | S & ~(1 << i) | or S ^ (1<<i) if you know it is present |
| Toggle \(i\) | S ^ (1 << i) | XOR is its own inverse |
| \(S\cup T,\ S\cap T,\ S\triangle T\) | S|T, S&T, S^T | one instruction each |
| Complement in \([n]\) | S ^ ((1<<n) - 1) | XOR with the full mask |
| \(|S|\) | S.bit_count() | popcount |
| Lowest element | (S & -S).bit_length() - 1 | \(x\ \&\ {-x}\) isolates the lowest set bit |
| Is \(T\subseteq S\)? | (S & T) == T | nothing outside \(S\) |
The identity behind lowbit: in two’s complement, \(-x=\lnot x+1\), which flips every bit above the lowest set bit and leaves that bit set. Hence \(x\ \&\ (-x)\) keeps precisely the lowest 1. Example: \(x=12=1100_2\), \(-x=\ldots10100_2\), \(x\ \&\ (-x)=100_2=4\).
Enumerating subsets and submasks
Bitmask DP
The signature use: the state contains ‘which items/cities have I already used?’, which is a subset, plus a small extra coordinate.
There are \(2^n n\) states and each takes \(O(n)\) work, so the total is \(O(2^n n^2)\) time and \(O(2^n n)\) memory - versus \((n-1)!\) for brute force. For \(n=20\): \(2^{20}\cdot400\approx4\times10^8\) (a few minutes in Python, seconds in C) against \(19!\approx1.2\times10^{17}\) (impossible). Exponential, but a survivable exponential - the exact distinction 19.14 teaches you to make.
Coding workbench
In the Euler Lab, bitmasks show up wherever the phrase ‘choose a subset’ or ‘which have I used?’ appears - digit-permutation problems, exact-cover-flavoured puzzles, and the smaller travelling-salesman variants in the Dynamic Programming path.
- Confusing & precedence in Python: S >> k & 1 works, but S & 1 << k == 0 does NOT mean what you think - parenthesise.
- Iterating \(k\in S\) by looping \(k=0..n-1\) and testing each bit when the mask is sparse. Use the lowbit loop instead.
- Believing bitmask DP makes an exponential problem polynomial. \(O(2^n n^2)\) is still exponential; it just moves the wall from \(n\approx12\) to \(n\approx20\).
- Allocating \(2^n\times n\) Python floats for \(n=25\) - that is 800 million cells. Check the memory before you write the loop (19.14).
- Forgetting that Python ints are signed and unbounded, so ~x is negative. Mask explicitly: x ^ ((1<<n)-1).
- int.bit_count() (Python 3.10+) is a single instruction on modern CPUs; below that, bin(x).count('1') is still surprisingly fast.
- Big-integer bitsets are CPython’s secret weapon: R |= R << v does thousands of DP updates in one operation. Reach for it whenever a boolean DP array is indexed by a sum.
- Order your subset loop by increasing mask value: since removing a bit always decreases the integer, \(S\setminus\{j\}\lt S\), so ascending mask order is automatically a valid topological order for the DP.
- The \(3^n\) submask sum is worth memorising: it is what makes subset-convolution and SOS (sum-over-subsets) DP practical at \(n=20\).
Practice this in the Euler Lab
Computational problems that exercise exactly this technique. Each opens in the Euler Lab with a Python workbench, a progressive hint ladder, and answer checking. Tier A/B run at full scale in the browser.
Warm-up:
#103 Special Subset Sums: Optimum (14%, tier C)
Applied:
#105 Special Subset Sums: Testing (21%, tier B) #106 Special Subset Sums: Meta-testing (21%, tier B) #944 Sum of Elevisors (22%, tier C)
Challenge:
#766 Sliding Block Puzzle (41%, tier C) #189 Tri-colouring a Triangular Grid (44%, tier C)
49 Project Euler problems in total are mapped to this lesson. Open the Euler Lab to filter them all.
Knowledge Check
Practical Exercise
(a) Prove that \(x\ \&\ (-x)\) isolates the lowest set bit, using the two’s-complement identity \(-x=\lnot x+1\). (b) You must decide whether any subset of 40 given integers sums to a target \(T\). Brute force is \(2^{40}\approx10^{12}\). Give a \(O(2^{n/2}n)\) algorithm. (c) State the exact memory cost of Held–Karp for \(n=22\) with 8-byte cells, and say whether it fits in 8 GB.
(a) Let the lowest set bit of \(x\) be at position \(k\), so \(x=\ldots b\,1\,\underbrace{0\cdots0}_{k}\). Then \(\lnot x=\ldots \bar b\,0\,\underbrace{1\cdots1}_{k}\) and adding 1 carries through those \(k\) ones, producing \(-x=\ldots\bar b\,1\,\underbrace{0\cdots0}_{k}\). Comparing \(x\) and \(-x\): below position \(k\) both are 0; at \(k\) both are 1; above \(k\) the bits are complementary. The AND therefore keeps only bit \(k\), i.e. \(x\ \&\ (-x)=2^k\).
(b) Meet in the middle (developed further in 19.10). Split the 40 numbers into halves \(A\) and \(B\) of 20. Enumerate all \(2^{20}\approx10^6\) subset sums of each half (a bitmask loop). Sort \(B\)’s sums. For each sum \(a\) of \(A\), binary-search \(T-a\) in \(B\)’s sorted list. Cost: \(O(2^{n/2}\cdot n)\) time (about \(2\times10^6\) sums plus \(10^6\log(10^6)\approx2\times10^7\) comparisons) and \(O(2^{n/2})\) memory. Feasible in seconds, versus \(10^{12}\) for brute force.
(c) States: \(2^{22}\times22=4{,}194{,}304\times22=92{,}274{,}688\) cells. At 8 bytes each that is \(738\ \text{MB}\) - which does fit in 8 GB as a C array, but in CPython, where each list element is a pointer to a boxed float (8 bytes pointer + ≥24 bytes object), the true footprint is several gigabytes and the allocation alone will take minutes. Use a flat array / NumPy buffer of float32 or int32 (369 MB) if you must run it at all.
Lesson Summary
Retrieval Practice
Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.
A: The first CLEARS the lowest set bit (\(x-1\) flips it and sets everything below); the second ISOLATES it (two's complement makes all higher bits complementary). Together they give an \(O(\text{popcount})\) element loop.
A: A mask with \(k\) bits has \(2^k\) submasks and there are \(\binom{n}{k}\) of them; \(\sum_k\binom nk 2^k=(1+2)^n=3^n\).
Completion Checklist
- I can explain the core ideas in my own words
- I worked the derivations/examples by hand
- I completed the interactive workbench(es)
- I passed the knowledge check