Bitset Optimization

May 2026 · 26 min read

A bitset packs many booleans into machine words and applies operations 64 bits at a time. In CP, this can turn O(n^3) into roughly O(n^3 / 64), or O(n * sum) knapsack into a tiny constant-factor shift-and-OR solution.

std::bitset

bitset<1000> a, b;
a.set(5);
a.reset(7);
a.flip(10);
auto c = a & b;
int cnt = c.count();

std::bitset<N> needs compile-time N. It is extremely fast and convenient when constraints are known.

Bitset Knapsack

For subset-sum reachability, bit s means sum s is reachable. Adding weight w shifts all reachable sums by w.

bitset<MAXS + 1> dp;
dp[0] = 1;
for (int w : weights) {
    dp |= dp << w;
}

bool can_make_x = dp[x];

This is one of the biggest practical wins from bit manipulation in DP.

Transitive Closure

Warshall's algorithm can use bitsets to OR reachability rows.

bitset<N> reach[N];
for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        if (reach[i][k]) reach[i] |= reach[k];
    }
}

The inner OR processes word chunks, making dense graph reachability much faster.

Graph Neighborhoods

Store each adjacency set as a bitset. Then intersection, union, and counting common neighbors become bit operations.

bitset<N> adj[N];

int common_neighbors(int u, int v) {
    return (adj[u] & adj[v]).count();
}

Dynamic Bitsets

When the size is only known at runtime, use a vector of 64-bit words.

struct DynBitset {
    vector<uint64_t> w;
    DynBitset(int n) : w((n + 63) / 64) {}

    void set(int i) { w[i >> 6] |= 1ULL << (i & 63); }
    bool test(int i) const { return (w[i >> 6] >> (i & 63)) & 1ULL; }
};

String DP Speedups

Bitsets can accelerate matching and LCS-like transitions by processing many positions at once. The details vary, but the core idea is to precompute character-position masks and update a bitset state per character.

Pitfalls

• std::bitset size must be a compile-time constant.
• Large bitsets on the stack can overflow; make them global or heap-allocated.
• Bitset speedups help dense boolean operations, not arbitrary per-state logic.
• Be careful with shifts larger than the bitset size; the result becomes all zero.

Practice Problems

• CSES - Money Sums knapsack bitset shift-and-OR.
• CSES - Reachable Nodes graph reachability bitsets on DAG reachability.
• Codeforces 914F - Substrings in a String string bitsets maintain character masks.
• LeetCode 416 - Partition Equal Subset Sum subset sum can be solved with bitset DP.