language-agnostic - 使用右移和按位与查找二进制数的模式？

Question

我正在尝试在汇编中编写一个函数，该函数将检测较长的二进制数是否包含较小的二进制模式。

示例：100111
是否包含1001？

当我读到这个问题时，我想我会在每次循环中右移（逻辑）时对大数字及其较小的模式进行按位与运算。

所以，在我的脑海里，我认为它会这样做：

100111 AND 1001 = 0  
Shift-right 1  
010011 AND 1001 = 0  
Shift-right 1  
001001 AND 1001 = 1 // Pattern FOUND!

并重复此操作，直到数字移动到零或 AND 返回 1。

但是，我想我一定有些困惑，因为在循环的第一次运行中，对于我放入的大多数内容，这将返回 1。我对 AND 的用法感到困惑吗？

score 5 · Accepted Answer

问题是“部分匹配”也会为您的 AND 检查返回一个非零值：

100111 AND 001001 = 000001

因此，这会测试是否有任何位匹配，但您要确保所有位都相同。AND 的结果需要等于您正在搜索的模式：

x = 100111
if (x AND 1001 == 1001)
  print "found"

score 1 · Accepted Answer

您应该 AND 然后针对搜索模式进行测试：

if ((TestPattern & SearchPattern) == SearchPattern)
{
   // then match
}

（其中&表示按位AND）

score 1 · Accepted Answer

按位与不能按您期望的方式工作（从样本判断并忽略似乎暗示您使用按位与作为位的逻辑与的符号）。AND 仅“考虑”设置为 1 的位。例如 1111 和 1001 == 1001。

您需要使用 XOR 并与 0 进行比较以进行匹配（请记住掩码您未从结果中比较的位）。在您的示例中，当 (N ^ 1001) & 1111 == 0000 时找到匹配项

score 1 · Accepted Answer

为了确保 0 和 1 位都与您的搜索模式匹配，您需要执行以下操作：

if ((InputPattern AND SearchMask) == SearchPattern)
{
    // then match
}

应该是全SearchMask1 位，长度等于您的 SearchPattern。例如，您可以拥有SearchMask == 1111, SearchPattern == 1001.

4 回答 4