In the “a” row, there’s a 0 for every instance of “a” in the pattern, as indexed into the corresponding bit array. The same applies to “b” and “c.” The letter “c” occurs in the 3rd and 4th place of the pattern, so the 3rd and 4th lower order bits are set to 0. Everything else is a 1.

Let’s match this pattern to the text “aaabcca,” which requires a separate bit array for keeping track of how far we’ve gotten, if we need to start over, etc. More precisely, this bit array keeps track of all matches of the current iteration. We initialize this bit array to `~1`

(not 1, `long`

format)

`1111111111111111111111111111110 # state`

Now, we iterate through the characters of our text “aaabcca.” Here’s where the bitwise operations come in. We 1) select the first letter of the text and bitwise-or the corresponding pattern bit matrix with our state and 2) left shift the state over 1:

Text **a**aabcca

`1111111111111111111111111111110 # pattern/a`

1111111111111111111111111111110 # old state

1111111111111111111111111111100 # new state

Awesome, a 0 indicates a match and a 1 indicates a mis-match at the corresponding position. So, so far, we’ve got a match of “a” and are ready to see if the next letter matches too. Next:

Text a**a**abcca

`1111111111111111111111111111110 # pattern/a`

1111111111111111111111111111100 # old state

1111111111111111111111111111100 # new state

We’ve still just got a match at “a”…

Text aa**a**bcca

`1111111111111111111111111111110 # pattern/a`

1111111111111111111111111111100 # old state

1111111111111111111111111111100 # new state

OK, I’m getting bored…

Text aaa**b**cca

`1111111111111111111111111111101 # pattern/b`

1111111111111111111111111111100 # old state

1111111111111111111111111111010 # new state

Text aaab**c**ca

`1111111111111111111111111110011 # pattern/c`

1111111111111111111111111111010 # old state

1111111111111111111111111110110 # new state

Text aaabc**c**a

`1111111111111111111111111110011 # pattern/c`

1111111111111111111111111110110 # old state

1111111111111111111111111101110 # new state

Suppose the pattern is of length `m`

. Each iteration checks the new state for whether the m+1th lowest bit is a 0. If it is, that means the pattern was matched to completion, like in this case! Awesome, we win.

Due to the limitation of this algorithm to strings of 31 characters or less, the runtime is O(1). The number of bitwise operations required is 2n, where n is the length of the text.