Bitmask Techniques
Compact subset state, fast bit operations, and the enumeration patterns that power many small-state solutions.
Bitmask Techniques
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Bitmasks are the natural representation when the state is a small subset of items. Instead of carrying a set object, I store one integer whose bits say which elements are present.
This is the bridge between straightforward brute force and the more structured subset DP techniques that appear later.
When to Use It
Use bitmasks when:
the universe size is small, usually \(n \le 20\) or a little more depending on the transition,
the state is a subset, partition, or visited-set condition,
checking or updating membership with bit operations is simpler than with containers,
you need to enumerate subsets, submasks, or supersets systematically.
Core Idea
Map item \(i\) to bit \(i\). Then: \[ \texttt{mask \& (1 << i)} \] tells me whether the item is present, while \[ \texttt{mask | (1 << i)} \] adds it.
The state becomes an integer, which means subset transitions are cheap and array indexing by mask becomes possible.
Key Insight
The real power is not compact storage. It is the ability to iterate over combinatorial states with simple arithmetic.
The most important loop is submask enumeration: \[ \texttt{for (sub = mask; ; sub = (sub - 1) \& mask)}. \] This visits every submask exactly once in descending order.
Operations / Main Technique
Membership and updates.
Test, add, remove, or toggle an element in \(O(1)\).
Enumerate all subsets.
Loop over \(\texttt{mask = 0 .. (1 << n) - 1}\).
Enumerate all submasks of one mask.
Useful for subset DP, partition transitions, and meet-in-the-middle postprocessing.
Worked example.
If \(mask = 13\), its binary form is \(1101_2\). That means items \(0, 2, 3\) are active. The submasks are \(1101, 1100, 1001, 1000, 0101, 0100, 0001, 0000\).
Correctness Intuition
Each bit represents one independent yes/no choice, so the mask gives a one-to-one encoding of subsets. Bitwise operations preserve that meaning exactly, which is why set transitions can be written as integer transitions.
For submask enumeration, the \(\texttt{(sub - 1) \& mask}\) step removes the lowest active bit and freely chooses smaller bits afterward, which is exactly what is needed to reach every submask once.
Complexity Analysis
test or update one bit: \(O(1)\),
enumerate all subsets of \(n\) items: \(O(2^n)\),
enumerate all submasks of one mask with \(k\) active bits: \(O(2^k)\),
many subset DP routines: \(O(n 2^n)\) or \(O(3^n)\) depending on the transition.
Implementation
The code includes basic helpers, submask enumeration, and one small routine that precomputes subset sums in \(O(n 2^n)\). That precomputation pattern appears often in DP and meet-in-the-middle tasks.
Common Pitfalls
Using \(\texttt{1 << n}\) with \(n \ge 31\) in 32-bit integers.
Forgetting that
__builtin_popcountis forunsigned int; use the 64-bit version when needed.Writing a submask loop that skips \(\texttt{0}\) by accident.
Treating \(2^n\) as cheap when \(n\) is already too large for the transition cost.
Variants / Extensions
Bitset acceleration when the state is large but operations are dense.
SOS DP and subset convolution.
Meet-in-the-middle by splitting the items into two halves.
State compression DP on grids or graphs.
Practice Problems
Traveling-salesman style DP on \(n \le 20\).
Count or optimize over all subsets with a compatibility condition.
Enumerate all partitions of a subset using submask loops.
Small-state BFS where the visited state includes a bitmask.
References
Code
Contest-ready reference implementation for the idea explained above.
bool has_bit(int mask, int bit) {
return (mask >> bit) & 1;
}
int set_bit(int mask, int bit) {
return mask | (1 << bit);
}
int clear_bit(int mask, int bit) {
return mask & ~(1 << bit);
}
vector<int> collect_submasks(int mask) {
vector<int> subs;
for (int sub = mask;; sub = (sub - 1) & mask) {
subs.push_back(sub);
if (sub == 0) {
break;
}
}
return subs;
}
vector<long long> subset_sums(const vector<long long>& weight) {
int n = (int)weight.size();
vector<long long> sum(1 << n, 0);
for (int mask = 1; mask < (1 << n); ++mask) {
int bit = __builtin_ctz(mask);
sum[mask] = sum[mask ^ (1 << bit)] + weight[bit];
}
return sum;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.