Bitset Optimization

Pack 64 boolean values into one machine word and operate on all of them at once. A 64× speedup that turns $O(n^2)$ into $O(n^2/64)$ — often the difference between $10^{10}$ and $1.6\cdot 10^8$.

std::bitset

bitset<100000> b;
b[i] = 1;  b.set(i);  b.reset(i);  b.flip(i);
b.count();                    // popcount, O(n/64)
b.any(); b.none(); b.all();
b |= c;  b &= c;  b ^= c;  b <<= k;  b >>= k;      // all O(n/64)
b._Find_first();              // first set bit  (GCC)
b._Find_next(i);              // next set bit after i  (GCC)

The size must be a compile-time constant. For a runtime size, use vector<uint64_t> and write the operations by hand.

The canonical wins

Subset sum — $O(nW/64)$

bitset<MAXW + 1> dp;
dp[0] = 1;
for (int x : items) dp |= dp << x;
bool reachable = dp[W];

$O(n\cdot W)$ becomes $O(nW/64)$. With $n=100$ and $W=10^5$ this is $1.5\cdot 10^5$ word operations — instant. See Subset Sum.

Reachability / transitive closure — $O(n^3/64)$

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];

Floyd-Warshall for reachability, 64× faster. For $n=2000$ that is $1.2\cdot 10^8$ word operations.

Boolean matrix multiplication

Store each row as a bitset; the product row is the OR of the rows selected by the set bits.

Bipartite matching on dense graphs

Keep each vertex’s neighbourhood as a bitset; “unvisited neighbours” is one AND, and iterating them uses _Find_next. Turns $O(VE)$ Kuhn into something usable on dense graphs.

Maximum clique

The pivot and candidate sets are bitsets; $P\cap N(u)$ is a single AND. This is what makes Bron-Kerbosch practical for $n\le 100$.

Longest common subsequence — $O(nm/64)$

The bit-parallel LCS (Crochemore-Iliopoulos-Pinzon) computes a whole DP row with a handful of word operations, using a precomputed match bitmask per character.

String matching

Bitap / shift-or simulate the matching NFA 64 states at a time.

Manual bitsets

When the size is dynamic:

struct Bitset {
    int n; vector<uint64_t> w;
    Bitset(int n) : n(n), w((n + 63) / 64, 0) {}
    void set(int i)   { w[i >> 6] |=  1ULL << (i & 63); }
    void reset(int i) { w[i >> 6] &= ~(1ULL << (i & 63)); }
    bool test(int i) const { return w[i >> 6] >> (i & 63) & 1; }
    void orWith(const Bitset& o) { for (size_t i = 0; i < w.size(); i++) w[i] |= o.w[i]; }
    int count() const { int c = 0; for (auto x : w) c += __builtin_popcountll(x); return c; }
};

Shifting by a non-multiple of 64 needs carry handling across words — write it once and keep it in a template.

When it pays

Signal
A boolean DP table	✔
$O(n^2)$ or $O(n^3)$ with a small constant needed	✔
Set operations on dense subsets	✔
The inner loop is a simple AND/OR/XOR over indices	✔
The inner loop has data-dependent branching	✘
Values are not boolean	✘ (unless you can decompose by bit)

Practical notes

• #pragma GCC target("avx2") can give another 2-4× on bitset operations, because the compiler vectorises the word loop. Combine with #pragma GCC optimize("O3").
• vector<bool> is also bit-packed, but its operator[] returns a proxy and it has no bulk operations — you cannot OR two vector<bool>s. Use bitset for the bit tricks.
• Iterating set bits with _Find_next is $O(\text{set bits}+n/64)$, not $O(n)$ — important for sparse bitsets.
• Memory: $n$ bits, so $10^7$ booleans is 1.25 MB instead of 10 MB.

The general lesson

Bitsets are the accessible form of word-level parallelism — the same idea behind fusion trees, Bitap, 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.

See also: Builtin Functions · Constant Factor Optimization · Space Optimization