vi. Bitset

Pack 64 booleans into a machine word and operate on all of them at once. That divides by $w=64$ and turns $10^{10}$ simple operations into $1.6\cdot 10^8$. With AVX2 pragmas the compiler processes 256 bits per instruction.

std::bitset

bitset<N> b;                     // N must be a compile-time constant
b.set(i); b.reset(i); b.flip(i); b[i];
b.count(); b.any(); b.none();
b |= c; b &= c; b ^= c; b <<= k; b >>= k;   // O(N / 64)
for (int i = b._Find_first(); i < N; i = b._Find_next(i)) {}   // iterate set bits (GCC)

For a runtime size, either pick the next power of two from a template list (template<int L> void solve() dispatched on $n$), or write a vector<ull> bitset by hand. Shifts across words need a carry from the neighbouring word.

Classic speedups

Problem	Bitset form	Cost
subset sum / 0-1 knapsack feasibility	dp |= dp << w	$O(nW/64)$
subset sum with bounded counts	binary splitting of multiplicities, then shifts	$O(W\sqrt{W}/64)$ when $\sum$ values $=W$ (at most $\sqrt{2W}$ distinct values)

Proof: dp |= dp << w and the $\sqrt{2W}$ distinct-value bound

The shift encodes the subset-sum transition. Represent “sums reachable so far” as a bitset where bit $s$ is set iff $s$ is reachable. Before considering item $w$, let $R$ be the reachable set; after optionally taking $w$, the new reachable set is $R\cup (R+w)=R\cup \{r+w:r\in R\}$ (either skip the item, keeping $R$, or take it, shifting every reachable sum up by $w$) — and $(R+w)$ as a bitset is exactly dp << w (shifting every set bit $s$ to position $s+w$), so $R\cup (R+w)$ is exactly dp | (dp << w). Applying this once per item, by induction the bitset after processing items $\mathrm{1..}i$ holds exactly the subset sums achievable using a subset of the first $i$ items, with $0$ always reachable (the empty subset) since bit $0$ of the initial dp is set and no shift ever clears it. $\sqrt{2W}$ bound. If the multiset of item values has $d$ distinct values $v_1<\cdots <v_d$ each appearing at least once, and the total sum is $W$, then since appearing at all requires contributing at least $v_i\ge i$ (as the values are distinct positive integers, the $i$-th smallest is at least $i$), $W\ge {\sum }_{i=1}^d{v}_i\ge {\sum }_{i=1}^{d}i=d(d+1)/2$, so $d\le O(\sqrt{2W})$. Binary-splitting each value’s multiplicity into $O(\log (\text{count}))$ power-of-two-sized chunks and shifting by each chunk (rather than one shift per original item) therefore costs $O(\sqrt{W}\log W)$ shifts rather than $O(n)$, each $O(W/64)$, dominating when $n\gg \sqrt{W}\log W$. $■$

Tested dp |= dp << w against an explicit $2^n$ subset-sum enumeration for $n$ up to 8, random positive weights, confirming the bitset after all items marks exactly the achievable sums.
| transitive closure | if (r[i][k]) r[i] \|= r[k] | $O(n^3/64)$ |
| DAG reachability counts for every vertex | reverse topological order, reach[v] \|= reach[u] | $O(nm/64)$; process in vertex chunks of 64·k to save memory |
| boolean matrix product | row $i$ of $AB$ = OR of rows $j$ of $B$ with $A_{ij}=1$ | $O(n^3/64)$ |
| triangles in a dense graph | (adj[u] & adj[v]).count() over edges | $O(nm/64)$ |
| bipartite matching / BFS on dense graphs | unvisited $\cap$ neighbours, _Find_first | $O(n^2/64)$ per BFS |
| maximum clique (Bron-Kerbosch) | $P\cap N(v)$ in one AND | practical up to $n\lesssim 100$ (Maximum Clique) |
| LCS | bit-parallel row update (Crochemore-Iliopoulos-Pinzon) | $O(nm/64)$ |
| pattern matching with wildcards / small alphabets | Shift-And / Bitap: D = ((D << 1) \| 1) & mask[c] | $O(nm/64)$ |
| all occurrences of a pattern in a string with updates | ans = all ones; ans &= (pos[p[j]] >> j) for each $j$ | $O(nm/64)$ per query |
| Gaussian elimination over ${\mathbb{F}}_2$ | rows as bitsets, XOR row operations | $O(n^3/64)$ |
| counting pairs with Hamming distance $\le k$ | popcount of XOR of rows | $O(n^{2}d/64)$ |
| 3D/4D dominance (offline) | one bitset per (dimension, threshold), AND them | $O(n^{2}d/64)$ |

Patterns

• Subset sum with reconstruction: keep a bitset per item (memory $nW/8$ bytes) or use divide and conquer on items.
• Knapsack where the answer is “which sums are possible”: bitsets beat the DP by 64x; with a count limit per value, group equal values and split into powers of two.
• Sliding-window or dynamic bitsets: maintain one bitset per value (positions where $a_i=v$); “positions $i$ such that $a_{i+j}=p_j$ for all $j$” is an AND of shifted bitsets.
• Bitset over the value domain for “does a pair with $a_i+a_j=s$ exist”: convolution would be FFT, but a bitset gives an $O(n\cdot V/64)$ alternative for moderate $V$.
• Offline queries in chunks: if $n$ bitsets of size $n$ don’t fit in memory ($n=10^5$ gives 1.25 GB), process vertices or queries in blocks of 64 or 4096 and reuse the memory.

When it pays

The inner loop is a simple AND/OR/XOR/shift over independent boolean entries, with no data-dependent branching. Values that aren’t boolean can sometimes be split by bit or by threshold. vector<bool> is also bit-packed, but it has no bulk operations, so it doesn’t count.

Practical: #pragma GCC target("avx2") gives a further 2-4x on bitset loops. Memory is $N/8$ bytes per bitset. Iterating set bits with _Find_next costs $O(\text{set bits}+n/64)$, not $O(n)$ — the win that matters for a sparse bitset.

Bitsets are the accessible form of word-level parallelism: the same “process 64 independent booleans per instruction” idea behind fusion trees (Theoretical Algorithms Catalog), Bitap/shift-or string matching, and the four-Russians technique. Whenever an inner loop does the same simple thing to many independent booleans, it can probably be done 64 at a time.