Algorithms
Advanced Bit Manipulation
Difficulty: Advanced
Iterating over all subsets of every subset of an n-element set sounds like 4^n work. The actual cost is 3^n: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum....
Advanced Bit Manipulation
Iterating over all subsets of every subset of an n-element set sounds like 4^n work. The actual cost is 3^n: each element is in three states (in the outer mask only, in both, or in neither), and the binomial theorem collapses the sum. Insights like that turn what looks like a complexity wall into a tight, elegant solution.
Advanced Bit Manipulation collects those insights. You will generate Gray codes (adjacent values differ by one bit, used in error correction), enumerate all subsets of a bitmask via the for (s = mask; s > 0; s = (s - 1) & mask) template, and master bit tricks like isolating the lowest set bit with x & -x, turning it off with x & (x - 1), counting trailing zeros, and swapping without a temp variable. The lesson also covers advanced XOR applications (range XOR, two missing numbers, XOR basis over GF(2)) and bitwise DP including profile DP for grid tiling.
In Bit Manipulation (Intro), you mastered the basic operators and the single-number XOR trick. This lesson treats bits as a full algorithmic medium.
Next, Complexity & Proof Intuition (Optional) revisits the theoretical foundations behind everything built so far.
Prerequisites:
Bit Manipulation (Intro)Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Generate Gray codes and explain the one-bit-difference property.
Enumerate all subsets of a bitmask and analyze the O(3^n) total complexity.
Apply advanced XOR tricks: range XOR, finding two missing numbers, and XOR basis.
Use bit tricks to isolate the lowest set bit, count trailing zeros, and iterate over set bits.
Implement bitmask DP for subset-based optimization problems.
Why This Matters
01
Gray codes ensure adjacent values differ by exactly one bit -- they are used in error correction, rotary encoders, and puzzle solving (Towers of Hanoi).
02
Subset enumeration using bitmasks is the foundation of exponential-time algorithms on small sets -- essential for competitive programming problems with n <= 20.
03
XOR-based techniques solve problems like finding two missing numbers or computing XOR of a range in constant time -- elegant tricks that appear in interviews.
04
Bitmask DP (profile DP) enables solving grid tiling and constraint satisfaction problems that would be intractable with other methods.
Key Terms
6 terms you'll encounter in this lesson
Gray Code
A sequence of binary numbers where adjacent values differ by exactly one bit. The n-bit Gray code has 2^n entries. Gray code for value i: i ^ (i >> 1).
Submask Enumeration
Iterating over all subsets of a given bitmask. For mask m, iterate: s = m; while s > 0 { process s; s = (s - 1) & m; }. Total across all masks of n bits is O(3^n).
Lowest Set Bit
The rightmost 1 bit in a number. Computed as x & (-x). For example, 12 (1100) has lowest set bit 4 (0100). Used in Fenwick trees and bit iteration.
XOR of Range [1,n]
XOR(1..n) follows a pattern: n%4==0: n, n%4==1: 1, n%4==2: n+1, n%4==3: 0. This allows computing range XOR in O(1) instead of O(n).
Bitmask DP
Dynamic programming where the state includes a bitmask representing which elements have been used/visited. Common in TSP (dp[mask][last]), assignment problems, and grid tiling.
Profile DP
A bitmask DP technique for grid problems where the bitmask represents the state of one column or row profile. Used for domino/tromino tiling problems.
Heads Up
Common misconceptions to watch out for
"Submask enumeration is O(2^n) for each mask"
For a mask with k bits set, it has 2^k submasks (not 2^n). Summing across all masks of n bits: sum over all masks m of 2^popcount(m) = 3^n. This is because each bit contributes a factor of 3 (0 in mask, 0 in submask | 1 in mask, 0 in submask | 1 in mask, 1 in submask).
"Gray code is just binary in a different order"
Gray code is a specific ordering where adjacent codes differ by exactly one bit. Binary counting can change many bits between consecutive values (e.g., 0111 -> 1000 changes 4 bits). Gray code guarantees only 1 bit changes, which is crucial for error-free mechanical encoders.
"x & (-x) gives the position of the lowest set bit"
x & (-x) gives the VALUE of the lowest set bit (a power of 2), not the position. For x = 12 (1100), x & (-x) = 4 (0100), which is 2^2. The position is 2, computed as log2(x & (-x)) or using count-trailing-zeros.