我面临以下问题：给定一个相对较短的位模式，我想找到它在合理的长位字符串中“适合”的位置。合适的是，对于在模式中设置的每个位，目标位字符串的对应位置都为零。
例如，可以在以下字符串中插入() => this.updateElements(i,j)
模式：
101101-“平凡”适合...00000000....-“完全匹配” ...10100101....-另一个有用的选择以此类推。
“适合”的质量无关紧要，应该按顺序排列第一个好人。
很显然，可以使用一种朴素的算法-通过对目标位字符串中的每个0进行迭代，我可以检查从该位置开始是否适合某个模式（调整模式中设置的首位）。
但是，据我们所知，较幼稚的实现，更专业的搜索算法可实现大幅提速。显然，“精确位模式搜索”算法无法解决此问题，但是考虑到收益，确切的模式搜索算法可提供比简单的实现更有效的方法，我希望了解是否有人已经投入了一些出色的工作来设计更好的算法用于描述的模式适合问题。
这取决于您要编写算法多少工作，但是您要描述的内容可以使用正则表达式解决。位模式101101与正则表达式0[01]00[01]0相对应。
很明显，将位字符串转换为实际的字符串，然后在其上使用实际的正则表达式将很慢。但是您可以使用正则表达式背后的思想来开发一种直接在位上工作的算法。关键思想是使用该模式来构建deterministic finite automaton。 DFA是一种状态机，它消耗您的位串的位，并根据当前位从一种状态转换为另一种状态。当它达到“接受”状态时，表明已找到一个匹配项，该位置在当前位结束。
将模式转换为状态机的最简单方法是使用Thompson's construction创建一个NFA，然后使用powerset construction将NFA转换为DFA。编写代码需要花费很多精力，但是生成的状态机应该能够测试位字符串是否匹配，并且如果仔细实施的话应该会非常高效。
与天真的O（nk）算法相比，测试位字符串的复杂度将为O（n），其中n是位字符串的长度，k是模式的长度。假设k小而n大，那么将模式转换为DFA所花费的时间应该可以忽略不计。
,假设您检查了比特流的最低位是否匹配，则将它们的副本放入了lowbits中。
首先执行异或运算：
lowbits = lowbits ^ pattern;
这样，应将应为零的位变为1，而我们不需要关心的位将保持不变。
然后执行位与运算：
lowbits = lowbits & pattern;
不计数的位（模式为0）被清除。
然后，当且仅当：
lowbits == pattern
如果没有找到匹配项，只需将比特流向右移动并继续即可。
如果该模式适合硬件寄存器，它将非常有效。否则，该模式将必须分解为硬件寄存器大小的块，并在每个块上重复该操作，直到失败为止。
可能存在加快比特流转移的策略（例如，将大小为p的模式分为大小为r的寄存器的n个块，那么您可以每{{1} }步骤，您可以在函数开始时将模式n*r-p+1左移一次，并将这些n*r-p+1例保留在内存中。