Bitset DP: Packing Boolean States into Machine Words

1. Introduction and Motivation

Many dynamic programming tables store nothing but a yes/no answer per state: is this sum reachable, is this position matched, is this configuration possible. A table like that is a row of booleans, and a row of booleans is exactly what a machine word already is. Instead of storing reachable[0], reachable[1], ..., reachable[m] as separate array cells and looping over them one at a time, you can store the entire row as the bits of a single integer, where bit $i$ means "state $i$ is reachable."

Once the row is a bitset, a transition that touches every state at once — such as "state $s$ becomes reachable if state $s - x$ was reachable" for every $s$ — collapses into one shifted OR: row = row | (row << x). A CPU executes that shift and that OR on all 32 or 64 bits of a word in a single instruction each, so an entire inner loop over the DP row is replaced by a small constant number of word-level operations. This is not a change in asymptotic complexity class in the strict sense — it is a division by the machine word width $w$ (typically 64) — but that constant factor is large enough to turn a borderline-too-slow DP into a fast one.

2. Prerequisites

This lesson assumes you are comfortable with basic bitwise operators. Bit Manipulation: Core Tricks & Interview Patterns covers &, |, ^, and shifts in detail and is the right place to build that fluency first; this lesson does not re-derive how a single shift or AND works; it only assumes you already read one as "move every bit left by $x$ positions" or "keep a bit only where both operands have it set."

The other prerequisite is the ordinary, one-state-at-a-time subset sum dynamic program. Knapsack & Coin Change Variants develops that DP and its 0/1 versus unbounded distinction in full, and it links back to this page for the bitset-acceleration technique applied to its Subset Sum variant. Read that lesson's Subset Sum section first if the recurrence reachable[s] = reachable[s] OR reachable[s - item] is not already familiar, since this lesson starts from that recurrence rather than deriving it from scratch.

3. A Concrete Example

Each row of the table is exactly the subset sums achievable from the items folded in so far: after all three items, the reachable set matches every subset sum of {3, 4, 5} (the empty set sums to 0, single items give 3, 4, 5, pairs give 7, 8, 9, and the full set gives 12). Bit 9 is set, so 9 is reachable via {4, 5}; bit 2 is never set at any step, so 2 is not a reachable sum from this item set.

4. Core Insight: Fast Boolean State Transitions

The naive DP visits every sum $s$ from high to low and asks "was $s - \text{item}$ already reachable." The bitset version asks the same question for every $s$ at once, because a left shift by item is precisely the operation "move whatever was true at $s - \text{item}$ to position $s$," for all positions simultaneously. Nothing about the recurrence changes; only the unit of work changes, from one bit to one machine word.

5. Bitset Subset Sum

Each panel below tests whether a target sum is reachable from a list of positive items, using the shift-and-OR recurrence from the previous section. Python's arbitrary-precision int grows to fit any sum, so no upper bound needs to be declared in advance. C++'s std::bitset<N> is fixed-size and must be declared with a compile-time capacity N large enough for the largest sum you will ever query; in exchange it is a flat array of machine words with no allocation per operation, which is faster than a dynamically sized big-integer when the maximum sum is known ahead of time. Java has no bitwise-shiftable fixed-size bitset built in, so BigInteger is the idiomatic choice — it behaves like Python's int, arbitrary precision with native shiftLeft/or/testBit methods.

def subset_sum_bitset(items, target):
    if target < 0:
        return False
    reachable = 1  # bit 0 set: sum 0 is always reachable
    for item in items:
        if item <= 0:
            raise ValueError("items must be positive")
        reachable |= reachable << item
    return (reachable >> target) & 1 == 1

items = [3, 4, 5]
print(subset_sum_bitset(items, 9))   # True  (4 + 5)
print(subset_sum_bitset(items, 2))   # False (2 is not a reachable subset sum)
print(subset_sum_bitset(items, 12))  # True  (3 + 4 + 5)

#include <bitset>
#include <iostream>
#include <vector>

constexpr int MAX_SUM = 1024; // must exceed the largest target you will query

bool subsetSumBitset(const std::vector<int>& items, int target) {
    if (target < 0 || target > MAX_SUM) return false;
    std::bitset<MAX_SUM + 1> reachable;
    reachable.set(0); // sum 0 is always reachable
    for (int item : items) {
        reachable |= (reachable << item);
    }
    return reachable.test(target);
}

int main() {
    std::vector<int> items{3, 4, 5};
    std::cout << std::boolalpha;
    std::cout << subsetSumBitset(items, 9) << '\n';   // true
    std::cout << subsetSumBitset(items, 2) << '\n';   // false
    std::cout << subsetSumBitset(items, 12) << '\n';  // true
}

import java.math.BigInteger;

public class BitsetSubsetSum {
    static boolean subsetSumBitset(int[] items, int target) {
        if (target < 0) return false;
        BigInteger reachable = BigInteger.ONE; // bit 0 set: sum 0 is always reachable
        for (int item : items) {
            reachable = reachable.or(reachable.shiftLeft(item));
        }
        return reachable.testBit(target);
    }

    public static void main(String[] args) {
        int[] items = {3, 4, 5};
        System.out.println(subsetSumBitset(items, 9));   // true
        System.out.println(subsetSumBitset(items, 2));   // false
        System.out.println(subsetSumBitset(items, 12));  // true
    }
}

The naive Subset Sum DP fills a boolean array of size $\text{sum}+1$ once per item, giving $O(n \times \text{sum})$ time. The bitset version performs the same number of OR-with-shifted-row operations, one per item, but each operation processes $w$ bits (a full machine word, typically 64) per underlying instruction instead of one bit per loop iteration. That gives $O(n \times \text{sum} / w)$, a constant-factor speedup of roughly $w$ that is easy to underestimate until you measure it: on large sums this routinely turns a multi-second naive DP into a sub-second bitset DP.

6. String DP Acceleration

Precompute, for each character $c$ that appears in the pattern, a mask with bit $i$ set wherever pattern[i] == c. Scanning the text one character at a time, shift state left by one (every partial match advances by one matched character), OR in a 1 at bit 0 (a match can always restart at the current position), then AND with the current character's mask (drop every partial match whose next required character does not equal the current text character). If the highest bit of state — bit $m-1$ for a pattern of length $m$ — becomes set, the whole pattern just matched ending at the current text position.

Tracing pattern "ab" against text "cab": charMask['a'] = 01, charMask['b'] = 10, charMask['c'] = 00, matchMask = 10 (bit 1). Start state = 00. Reading c: ((00<<1)|1) & 00 = 00. Reading a: ((00<<1)|1) & 01 = 01 (the "a" alone has matched). Reading b: ((01<<1)|1) & 10 = 11 & 10 = 10, and bit 1 is set, so "ab" matches ending at this position — the match starts at index 1, since a match of length 2 ending at text index 2 starts at $2-2+1=1$.

def shift_and_search(text, pattern):
    m = len(pattern)
    if m == 0:
        return []
    match_mask = 1 << (m - 1)
    char_masks = {}
    for i, ch in enumerate(pattern):
        char_masks[ch] = char_masks.get(ch, 0) | (1 << i)
    state = 0
    matches = []
    for j, ch in enumerate(text):
        state = ((state << 1) | 1) & char_masks.get(ch, 0)
        if state & match_mask:
            matches.append(j - m + 1)
    return matches

print(shift_and_search("cab", "ab"))        # [1]
print(shift_and_search("abcabcab", "cab"))  # [2, 5]

#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

std::vector<int> shiftAndSearch(const std::string& text, const std::string& pattern) {
    std::vector<int> matches;
    int m = static_cast<int>(pattern.size());
    if (m == 0 || m > 63) return matches; // fits in one 64-bit word
    uint64_t matchMask = 1ULL << (m - 1);
    std::unordered_map<char, uint64_t> charMasks;
    for (int i = 0; i < m; ++i) {
        charMasks[pattern[i]] |= (1ULL << i);
    }
    uint64_t state = 0;
    for (int j = 0; j < static_cast<int>(text.size()); ++j) {
        uint64_t mask = charMasks.count(text[j]) ? charMasks[text[j]] : 0ULL;
        state = ((state << 1) | 1ULL) & mask;
        if (state & matchMask) {
            matches.push_back(j - m + 1);
        }
    }
    return matches;
}

int main() {
    for (int idx : shiftAndSearch("cab", "ab")) std::cout << idx << ' ';
    std::cout << '\n'; // 1
    for (int idx : shiftAndSearch("abcabcab", "cab")) std::cout << idx << ' ';
    std::cout << '\n'; // 2 5
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ShiftAndSearch {
    static List<Integer> search(String text, String pattern) {
        List<Integer> matches = new ArrayList<>();
        int m = pattern.length();
        if (m == 0 || m > 63) return matches; // fits in one 64-bit word
        long matchMask = 1L << (m - 1);
        Map<Character, Long> charMasks = new HashMap<>();
        for (int i = 0; i < m; i++) {
            char c = pattern.charAt(i);
            charMasks.merge(c, 1L << i, (a, b) -> a | b);
        }
        long state = 0L;
        for (int j = 0; j < text.length(); j++) {
            long mask = charMasks.getOrDefault(text.charAt(j), 0L);
            state = ((state << 1) | 1L) & mask;
            if ((state & matchMask) != 0) {
                matches.add(j - m + 1);
            }
        }
        return matches;
    }

    public static void main(String[] args) {
        System.out.println(search("cab", "ab"));       // [1]
        System.out.println(search("abcabcab", "cab")); // [2, 5]
    }
}

This is the same acceleration as bitset Subset Sum applied to a different DP: the underlying recurrence for exact string matching is a boolean transition over "how many pattern characters matched so far," and packing that dimension into one word lets a single shift-and-mask update the entire match-progress row per text character, instead of a nested loop over pattern positions.

7. Complexity Analysis

For bitset Subset Sum, $n$ is the number of items and $m$ is the target sum, so naive $O(n \times \text{sum})$ becomes $O(n \times \text{sum} / w)$. For Shift-And string matching, $n$ is the text length and $m$ is the pattern length, so the naive automaton simulation's $O(n \times m)$ (or a naive character-by-character comparison's worst case $O(n \times m)$) becomes $O(n \times m / w)$ whenever the pattern fits in one machine word; longer patterns need $\lceil m / w \rceil$ words and correspondingly $\lceil m/w \rceil$ times the per-character work, still far fewer operations than one comparison per pattern position.

8. Applications and Alternatives

9. Exercises and Mastery

Easy

1. Using the bitset Subset Sum code, check whether the set [2, 6, 9] can reach the target 15. Trace the bitset by hand after each item, the way the worked example did for [3, 4, 5].
2. Extend the same code to also report the smallest reachable sum that is greater than or equal to a given target, using reachable after all items are folded in.

Medium

1. Extend bitset Subset Sum to reconstruct which items were chosen for a reachable target. A single final bitset only tells you a sum is reachable, not by which items, because the OR has merged every path into one word. The standard workaround is to keep one bitset snapshot reachable_i after processing each of the first $i$ items (an array of $n+1$ bitsets), then walk backward from $i = n$: if bit $s$ is set in reachable_i but not in reachable_{i-1}, item $i$ was necessarily used to reach $s$, so record it and continue the search from reachable_{i-1} at $s - \text{item}_i$; otherwise item $i$ was not needed for this particular reconstruction, and you continue from reachable_{i-1} at the same $s$. This costs $O(n)$ extra bitsets of memory in exchange for full traceability.
2. Adapt the Shift-And code to count, rather than list, how many text positions the pattern matches, without storing the match list.

Hard

1. Use bitset acceleration to speed up counting the number of distinct subsequences of a text that equal a given pattern. The naive DP is $O(n \times m)$ over a boolean-or-count table indexed by (text position, pattern position); when only reachability of "pattern fully consumed" matters rather than the exact count, the same per-character bitset used in Shift-And can determine in $O(n \times m / w)$ whether at least one occurrence exists, though recovering an exact count still requires care since counts, unlike booleans, do not compress into single bits without additional bookkeeping (e.g., splitting the count DP across several bitsets to represent low-order bits, similar to how a binary adder is built from single-bit gates).

Review rhythm: tomorrow, rederive reachable = reachable | (reachable << item) from the plain recurrence without looking it up; next week, implement the Shift-And trace by hand on a pattern you pick yourself; several weeks later, look for a third DP in your own work whose transition is a boolean OR or AND over a large dimension, and pack it into a bitset the same way.

10. Summary Cheat Sheet

• A boolean DP row is a bitset waiting to happen: bit $i$ of one integer replaces a whole array cell reachable[i].
• Subset Sum's reachable[s] = reachable[s] OR reachable[s - item] becomes reachable = reachable | (reachable << item) as a single word-parallel step.
• Naive $O(n \times \text{sum})$ becomes $O(n \times \text{sum} / w)$; naive $O(n \times m)$ string matching becomes $O(n \times m / w)$, where $w$ is the machine word size, typically 64.
• Python's arbitrary-precision int, C++'s std::bitset<N>, and Java's BigInteger are the three idiomatic carriers for this technique, trading fixed capacity for allocation-free speed or vice versa.
• Shift-And packs "how much of the pattern has matched" into one word and updates it per text character with state = ((state << 1) | 1) & charMask[c].
• The technique loses per-item or per-position bookkeeping; reconstructing which choices were made requires extra bitset snapshots or an auxiliary structure, not just the final bitset.
• Reach for a Fenwick tree or segment tree instead when the workload needs point updates or range queries over time, rather than a single left-to-right fold.