◄ WORLD V · SONNY 5DART 119 · a helldive at the net

SHIFT-OR a search automaton in one machine word

Carry a whole string-search automaton inside a single integer. Precompute a bitmask per character (bit j is 0 where the pattern has that char at position j). Then per text character: R = (R << 1) | mask[c]. When the high bit of R drops to 0, the pattern just matched. No tables the size of the text, no backtracking — and it extends to fuzzy matching by carrying a few extra words.

THE TECHNIQUE shift a bitmask, watch the high bit fall

Each pattern character gets a mask with a 0 at the positions it occupies. State R starts all-ones. Reading text char c, shift R left and OR in mask[c]; a run of matched characters walks a 0 up through R, and when bit m−1 reaches 0 the whole pattern has matched. Type a text and pattern; watch R evolve in binary. live demo


  






  
HISTORY & CREDIT named 1989, published 1964

  
“Shift-Or is Shift-And” — no; the original is Shift-OR, where 0 means match (counter-intuitive) and it saves one op per char. cited

  

    1964 · Balint Domolki (Hungarian Academy of Sciences) publishes the bit-vector nondeterministic recognizer — the shift-and-mask automaton — for syntactic analysis (parsing), ~25 years early.

    1989/1992 · Ricardo Baeza-Yates & Gaston Gonnet independently re-derive it as Shift-Or for text search (PhD thesis; CACM 35(10), 1992). Genuine reinvention — but not first.

    1991/1992 · Sun Wu & Udi Manber extend the bit-parallel method to insertions and deletions (true edit distance) and ship agrep — the fuzzy matching people wrongly credit to Baeza-Yates.

    the nickname · “bitap” (bit-parallel approximate) appears in neither original paper — a later gloss; a confident etymology should be hedged.
  

  
Don’t over-correct the other way: Domolki built a parser recognizer, not “the bitap algorithm” — string search is genuinely Baeza-Yates & Gonnet’s reading. Baeza-Yates & Gonnet, 1989/1992






  
RECOMMEND FOR I-13 shift, OR, mask — pure bitwise

  
The whole automaton is one integer and two bitwise ops per character — and the match lands where it should:

  
$ i13 run shor.i13    # pattern "abc" (3 bits), masks a=110 b=101 c=011
R: 7 -> 6 -> 6 -> 5 -> 3     reading a,a,b,c
bit2 of final R = 0  ->  MATCH ending at index 3 (start 1)

  

    Recommend: nothing new — the masks are an f64 array indexed by code point; the state is one integer; each step is (R << 1) | mask masked to m bits (bitwise, dart 029), and the match test is R & (1<<(m−1)) == 0 (verified R walks 7→6→6→5→3, high bit clears, match at index 3). O(1) extra space survives directly on bounded arrays.

    Note: it joins the standing string family (Boyer-Moore 061, KMP 063) — but where those precompute size-m pattern tables, Shift-Or carries the whole matcher state in one machine word (its only table is the small per-character mask, size of the alphabet, not the pattern).