Competitive Programming Bit Pattern Catalog

May 2026 · 28 min read

Advanced bit manipulation is mostly pattern recognition. You see constraints, operations, and required outputs, then map the problem to one of a small number of techniques. This catalog is the "which hammer do I reach for?" page.

Constraint Map

Signal	Likely technique	Why
`n <= 20`, subsets	Bitmask DP	`2^n` states may fit.
All submasks for every mask	SOS DP	Replace O(3^n) with O(n * 2^n).
Pair result by XOR	Binary trie or FWT	Trie for max/min/count with online values; FWT for full convolution.
Maximum subset XOR	XOR linear basis	Subset XOR values form a vector space over GF(2).
Boolean DP with large sum/graph width	Bitset optimization	Process 64 booleans per CPU word.
Maximize answer bit-by-bit	Bitwise greedy	Higher bits dominate lower bits if feasibility is monotonic.
Game with independent piles/components	Nim/Grundy XOR	Independent impartial games combine by XOR.

XOR: Trie vs Basis vs Prefix

Prefix XOR: use when asking range XOR or subarray XOR.
Binary trie: use when pairing a query value with one stored value to maximize/minimize/count XOR.
Linear basis: use when choosing any subset to maximize or represent XOR.
FWT: use when counting all pairs by XOR result over arrays indexed by masks.

Bitmask DP Checklist

What does one bit represent?
What does dp[mask] mean exactly?
Do transitions add one bit, remove one bit, split a mask, or merge submasks?
Is the complexity O(n * 2^n), O(3^n), or worse?
Can SOS DP, bitsets, or meet-in-the-middle reduce it?

Debugging Checklist

Print masks with bitset<N> while debugging.
Check whether bit positions are 0-indexed or 1-indexed in the statement.
Use 1LL << k for 64-bit masks.
Guard zero before clz or ctz.
Confirm whether the problem wants a value, count, minimum cost, or existence.
For XOR, decide whether you are pairing values, choosing subsets, or querying ranges.

Interview vs CP Emphasis

Interviews usually emphasize clarity, invariants, and edge cases: single number, reverse bits, sum without plus, range AND, UTF-8 validation. CP pushes further into tries, SOS DP, FWT, linear basis, bitsets, and game XOR invariants.

Practice Problems

LeetCode 136 - Single Number XOR invariant start simple.
LeetCode 421 - Maximum XOR trie/greedy two standard approaches.
CSES - Elevator Rides bitmask DP exact state definition.
CSES - Bit Problem SOS DP subset/superset counting.
Codeforces 845G - Shortest Path Problem? linear basis graph cycles and XOR basis.