vii. Bitset and Word-Level Parallelism

A machine word holds $w=64$ booleans, and one instruction processes all of them. Any DP or set operation whose inner loop is a boolean OR / AND / XOR / shift over an array can run $64\times$ faster: $O(n^2)\to O(n^2/64)$, $O(n^3)\to O(n^3/64)$. With $n=10^4$, $n^3/64\approx 1.6\cdot 10^{10}$ is still too slow, but $n^2\cdot 10^4/64$ style bounds (about $10^9$ simple word operations) pass in a few seconds. The basics of std::bitset are in Bitset.

Problem	Plain	Word-parallel
subset sum up to $S$ with $n$ items	$O(nS)$	$O(nS/64)$
LCS of strings of length $n,m$	$O(nm)$	$O(nm/64)$
transitive closure	$O(n^3)$	$O(n^3/64)$
count triangles	$O(n^3)$ or $O(m\sqrt{m})$	$O(n^3/64)$
boolean matrix product	$O(n^3)$	$O(n^3/64)$ (Four Russians: $O(n^3/(w\log n))$)
Gaussian elimination over GF(2)	$O(n^3)$	$O(n^3/64)$
“is there a pair/triple with property” over sets	$O(n^2\cdot k)$	AND of two bitsets, then any()

Subset sums, closure, triangles

template<int N> bitset<N> subsetSums(const vector<int>& a) {   // bit s set iff some subset sums to s (s < N)
    bitset<N> b; b[0] = 1;
    for (int x : a) b |= b << x;
    return b;
}
 
template<int N> vector<bitset<N>> transitiveClosure(vector<bitset<N>> g, int n) {   // O(n^3 / 64)
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++) if (g[i][k]) g[i] |= g[k];
    return g;
}
template<int N> long long countTriangles(const vector<bitset<N>>& adj, int n) {
    long long c = 0;
    for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) if (adj[i][j]) c += (adj[i] & adj[j]).count();
    return c / 3;
}

Proof: the shifted-OR recurrences

Subset sums. After processing items $a_1..a_i$, bit $s$ is set iff $s$ is a subset sum of them: true for $i=0$; and $s$ is a subset sum of the first $i$ items iff it is one of the first $i-1$ (bit already set) or $s-a_i$ is (bit set by b << a_i). Closure. This is Warshall’s algorithm: after processing intermediate vertex $k$, row $i$ contains every vertex reachable from $i$ using intermediates in $\{\mathrm{0..}k\}$; if $i$ reaches $k$, everything $k$ reaches is OR-ed in. Triangles. For each edge $(i,j)$ with $i<j$, the AND of the neighbourhoods counts common neighbours; each triangle is counted once per edge, so three times.

LCS in O(nm/64)

Encode a DP row by its differences: bit $j$ of $V$ is $0$ where the row value increases. Each character of $s$ updates all $m$ columns at once with one addition, one subtraction and a few logic operations, carried across words:

int lcsBitParallel(const string& s, const string& t) {      // O(|s| * |t| / 64): V <- (V + U) | (V - U), U = V & match
    int m = sz(t), W = (m + 63) / 64;
    vector<vector<ull>> match(256, vector<ull>(W, 0));
    for (int j = 0; j < m; j++) match[(unsigned char)t[j]][j >> 6] |= 1ULL << (j & 63);
    vector<ull> V(W, ~0ULL);                                 // zero bits of V (among the first m) = LCS length
    for (char c : s) {
        const auto& M = match[(unsigned char)c];
        ull carry = 0, borrow = 0;
        for (int k = 0; k < W; k++) {
            ull u = V[k] & M[k];
            ull s1 = V[k] + u, c1 = s1 < u, s2 = s1 + carry, c2 = s2 < s1;
            ull d1 = V[k] - u, b1 = V[k] < u, d2 = d1 - borrow, b2 = d1 < borrow;
            V[k] = s2 | d2; carry = c1 | c2; borrow = b1 | b2;
        }
    }
    int ones = 0;
    for (int k = 0; k < W; k++) {
        ull w = V[k];
        if (k == W - 1 && m % 64) w &= (1ULL << (m % 64)) - 1;
        ones += __builtin_popcountll(w);
    }
    return m - ones;
}

Proof sketch: the bit-vector LCS update

Let $L_i(j)$ be the LCS of $s_{\mathrm{1..}i}$ and $t_{\mathrm{1..}j}$; consecutive values differ by $0$ or $1$, so row $i$ is encoded by the 0/1 vector of increments ($V$ stores the complement, $1$ = no increment). In row $i+1$, within each segment of $V$ ending at an increment, the new increment moves to the leftmost match position of the segment, if any. Adding $U=V\&M_c$ to $V$ makes the carry run from each matched position to the end of its run of ones, which clears exactly those leftmost matches and sets the right bits; OR-ing with $V-U$ restores the bits that the carry wrongly cleared. This is the Allison–Dix / Hyyrö recurrence; the number of zero bits is $L_{|s|}(m)$. Tested against the $O(nm)$ DP on random strings over alphabets of size $\mathrm{1..4}$.

Rules of thumb

• std::bitset<N> needs a compile-time $N$; for run-time sizes use a vector<ull> with manual shifts, or a template recursion over sizes ($N=64,128,256,\dots$) to pick the smallest bitset that fits.
• Shifts by $x$ cost $O(N/64)$ each; OR-ing $n$ shifted copies is $O(nN/64)$.
• _Find_first() and _Find_next(i) iterate set bits in $O(N/64+\text{count})$.
• Popcount: __builtin_popcountll, or bitset::count().

Related: Bitset, Knapsack, Sequence DP.