使用shift-right和bitwise-AND找到二进制数的模式？

Question

我正在尝试在程序集中编写一个函数,它将检测更长的二进制数是否包含更小的二进制模式.

示例:100111
是否包含1001？

当我读到这个问题时,我想我会用一个大数字及其较小的模式进行按位-AND,同时每次在循环中右移(逻辑).

所以,在我的脑海里,我认为它会做:

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

并重复此操作,直到数字被移动直到它为零或AND返回1.

但是,我想我必须有一些困惑,因为在第一次循环运行时,我输入的大部分内容都会返回1.我对AND的使用感到困惑吗？

Answer 1

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

100111 AND 001001 = 000001

因此,如果任何位匹配,则测试,但是您要确保所有位都相同.AND的结果需要等于您搜索的模式:

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