Bitap: Packing String Matching into One Bit Operation

The bitap algorithm finds a pattern in a text stream by packing match states into a single 64-bit integer. It works best when the pattern is shorter than the machine word width, typically under 64 characters.

The derivation starts from brute force, step by step. It begins with a naive loop, then forces a one-pass constraint. The key move is replacing a list of active states with a bitset.

Shifting left advances all states at once. A precomputed mask then kills invalid transitions. The final logic reduces to a shift, an AND, and a check.

This is elegant because it turns a linear scan of states into constant-time bit operations. It is not a universal replacement for KMP or Boyer-Moore, but for short patterns in streaming data, it is hard to beat.

The explanation is clear enough to implement in an afternoon. Skip it if your patterns are long or if you already know the shift-and technique.

Read the derivation, then try implementing the core three lines in a language with native 64-bit integers.