Packing bits
A bitset stores a sequence of true or false values packed tightly into machine words, one bit each. Because the processor operates on a whole word at a time, a single bitwise instruction handles dozens of bits together. That parallelism is the source of the speedup.
Where it helps
Many algorithms that fill a boolean table can be rewritten with bitsets. For example, a subset sum table that marks which sums are reachable can shift and combine entire rows with shift and or operations, advancing many sums in one instruction. Dynamic programming over reachable states, transitive closure of a graph, and certain string matching tables all benefit.
The wins are:
- Less memory, since each value is a single bit rather than a byte or word.
- Fewer instructions, since each operation covers a word's worth of values at once.
What it does and does not change
A bitset reduces the work by a constant factor tied to the word width. It does not change the fundamental shape of the algorithm, so a slow approach stays slow in the big picture. But that constant factor often turns a borderline solution into a comfortably fast one.
Key idea
Pack booleans into words so one bitwise instruction updates many values, cutting time and memory by a constant factor.