Phase 19 - Lesson 19.8

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.

⏱ 60 min● Advanced🔗 Prereqs: 19.7 dynamic programming

↖ Phase 19 hub

Builds on: 19.7 needed a compact state; a bitmask IS the compact state when the state is ‘which subset have I used?’.
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

Intuition

A subset of \(\{0,\dots,n-1\}\) is a list of yes/no answers - and a list of yes/no answers is a binary number. Once you see that, the set operations become single CPU instructions and the DP table becomes a flat array indexed by the subset itself. The catch is honest and permanent: there are \(2^n\) subsets. Bitmask DP does not defeat exponential growth; it makes the exponent small enough to survive (roughly \(n\le20\) for \(2^n n^2\)).

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

\[\text{all subsets: } S=0,1,\dots,2^n-1.\qquad \text{all submasks of }M:\quad s=M;\ \ \text{while } s:\ \ \{\text{use }s\};\ \ s=(s-1)\ \&\ M.\] (19.18)

Theorem - The \(3^n\) bound

Summing the number of submasks over all masks gives \(\sum_{M\subseteq[n]}2^{|M|}=\sum_{k=0}^n\binom nk 2^k=(1+2)^n=3^n\) by the binomial theorem. So the nested ‘for each mask, for each submask’ loop is \(O(3^n)\), not \(O(4^n)\) - a distinction that decides feasibility around \(n=20\) (\(3^{20}\approx3.5\times10^9\) vs \(4^{20}\approx1.1\times10^{12}\)).

Bitmask DP

The signature use: the state contains ‘which items/cities have I already used?’, which is a subset, plus a small extra coordinate.

Definition - Held–Karp (TSP)

Let \(D[S][j]\) be the length of the shortest path that starts at city 0, visits exactly the set \(S\) (with \(0,j\in S\)), and ends at \(j\). Then

\[D[S][j]=\min_{i\in S\setminus\{j\}}\Big( D[S\setminus\{j\}][i] + w(i,j)\Big),\qquad \text{answer}=\min_j \big(D[\text{full}][j]+w(j,0)\big).\] (19.19)

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.

Worked Example - Subset-sum reachability with a single integer

Question: from \(\{3,34,4,12,5,2\}\), which totals \(\le 20\) are achievable?

Represent the set of reachable sums as ONE big integer \(R\), where bit \(t\) is set iff total \(t\) is reachable. Start \(R=1\) (only 0 is reachable).

Adding an item of value \(v\) to the pool: every previously-reachable \(t\) now also gives \(t+v\). Shifting all bits up by \(v\) does that in one operation: R |= R << v.

Process 3, 34, 4, 12, 5, 2 in turn. After all six items, bit \(t\) of \(R\) is set iff some sub-multiset sums to \(t\).

Check \(t=9\): \(3+4+2=9\) ✓, so bit 9 is set. Check \(t=11\): \(4+5+2=11\) ✓. Check \(t=1\): no subset sums to 1, so bit 1 is clear.

Cost: \(O(n)\) big-integer shifts on a \(\Sigma v\)-bit integer - in CPython this beats an explicit boolean DP array by an order of magnitude, because the bit-parallelism happens inside the big-int machinery. Same \(O(n\Sigma)\) work; a far better constant.

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.

Common Mistakes to Avoid

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).

Quant Practitioner Tips

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

Q1 Medium

x & (x-1) computes:

x with the lowest set bit cleared

The lowest set bit

The popcount

x divided by 2

Q2 Hard

Looping over all masks and, for each, all of its submasks costs:

\(O(2^n)\)

\(O(4^n)\)

\(O(3^n)\), by \(\sum_k\binom nk 2^k=3^n\)

\(O(n2^n)\)

Q3 Medium

Held–Karp solves TSP in \(O(2^n n^2)\). At roughly what \(n\) does this stop being feasible on a normal machine?

Around n = 8

Around n = 20

Around n = 100

It is polynomial, so any n

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.

▶ Show full solution

(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.

After the reveal, answer for yourself: Part (c) is the lesson: the asymptotic bound said ‘fits’, the language’s constant factor said ‘no’. Which of the two would you have checked first before this lesson?

Lesson Summary

A subset is an integer, so set operations become single bit operations and a DP indexed by subsets becomes a flat array. Popcount, x & (x-1) (clear lowest bit) and x & -x (isolate lowest bit) give tight inner loops; submask enumeration over all masks costs \(3^n\), not \(4^n\). Held–Karp solves TSP in \(O(2^n n^2)\), and the big-integer trick R |= R << v performs subset-sum reachability in bit-parallel. None of this defeats exponential growth - it just makes \(n\le20\) survivable.

Retrieval Practice

Close the lesson and answer from memory before checking. This is deliberate, effortful recall - the single highest-yield study action.

▶ Show retrieval prompts & answers

Q: What do x & (x-1) and x & -x do, and why?
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.

Q: Why is ‘for each mask, for each submask’ \(O(3^n)\)?
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

Confidence / mastery rating

Personal notes

Source References

This lesson synthesizes and paraphrases concepts from the sources below. No copyrighted text, problem sets, or solutions are reproduced. Return to the originals for full depth.

The Pragmatic Programmer (Thomas & Hunt, 2nd/20th Anniv. ed., 2019) current - Ch. 3 & Ch. 7 - Choosing a representation that makes the operation trivial: encoding a subset as an integer is the canonical example of letting the data structure do the work.
Calculus, Vol. I (Tom Apostol, 2nd ed., 1967) foundational - Ch. I.4 - The binomial theorem, which is exactly what proves the \(3^n\) submask bound.
Numerical Linear Algebra (Trefethen & Bau, SIAM, 1997) foundational - Lecture 32 - Counting operations and memory before running anything - the discipline that tells you Held–Karp dies at \(n\approx25\).

← 19.7 Next: 19.9 →