Bitset Optimization
Use machine-word parallelism to update or compare dozens of boolean states with one operation.
Bitset Optimization
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Bitset optimization is the habit of rephrasing boolean-state transitions so that one machine word updates 64 states at once. In competitive programming this often turns borderline \(O(n^2)\) boolean DP or dense-graph processing into something that actually passes.
When to Use It
It is especially effective when:
the state is yes/no rather than numeric,
the transition is based on shifts, AND, OR, XOR, or intersection,
the dimension is large enough that a \(64\times\) constant-factor improvement matters.
Core Idea
Store a boolean array as packed bits instead of bools. Then operations such as \[ \texttt{reachable |= reachable << w} \] update many states at once.
Key Insight
The optimization is not magic. It works because the CPU already knows how to shift, mask, and combine entire words very quickly. If the transition can be written in those operations, you get parallelism ``for free'' without threads or SIMD intrinsics.
Worked Problem
Problem.
Given positive integers \(a_1, a_2, \dots, a_n\) with total sum at most \(S\), determine which subset sums are reachable.
Why bitsets fit.
The ordinary DP is \[ \texttt{dp[s] = dp[s] or dp[s - a_i]}. \] With a bitset, one item update becomes dp |= dp << a_i. That replaces \(O(S)\) scalar transitions with \(O(S / 64)\) word operations.
Problem Pattern
The same trick appears in:
subset-sum and knapsack reachability,
dense graph transitive closure with row bitsets,
maintaining large character sets or forbidden masks,
fast set intersections in Mo-style or offline problems.
Correctness Intuition
The packed representation does not change the DP semantics. Bit \(s\) is still ``sum \(s\) is reachable.'' The bit operations merely update 64 such booleans in parallel.
Complexity Analysis
If the original boolean DP is \(O(NM)\), the bitset version is usually \(O(NM / W)\), where \(W\) is the machine word size, typically \(64\).
Implementation
The sample code gives a reusable subset-sum bitset wrapper. In actual contest code I often use std::bitset for compile-time bounds and a manual vector<uint64_t> wrapper when the bound is only known at runtime.
Common Pitfalls
Applying bitsets to numeric DP where each state stores a large value, not a boolean.
Forgetting the memory cost; a bitset of size \(10^7\) is already noticeable.
Using
std::bitsetwhen the size is only known at runtime.Expecting asymptotic improvements when the transition itself is not bit-parallel.
Variants / Extensions
Manual dynamic bitsets with
uint64_t.Bitset adjacency rows for dense graph BFS or transitive closure.
Using
__builtin_popcountllon words to count set bits quickly after intersections.
Practice Problems
Subset-sum reachability with large total sum.
Dense graph reachability or clique-style adjacency intersections.
Any boolean DP whose transition is shift-or-mask based.
References
Code
Contest-ready reference implementation for the idea explained above.
template <int MAX_SUM>
struct SubsetSumBitset {
bitset<MAX_SUM + 1> reachable;
SubsetSumBitset() {
reachable[0] = 1;
}
void add_value(int x) {
reachable |= (reachable << x);
}
bool can_make(int sum) const {
return 0 <= sum && sum <= MAX_SUM && reachable[sum];
}
vector<int> all_reachable_sums() const {
vector<int> sums;
for (int sum = 0; sum <= MAX_SUM; ++sum) {
if (reachable[sum]) sums.push_back(sum);
}
return sums;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.