在 Python 中搜索整数中的位序列

首先，要做到这一点，Python是一种糟糕的语言 Select .无论如何，你都会做很多小打小闹的事情.为了方便程序员，Python是一种具有较慢抽象层的高级语言.这给任何看起来简单的比特旋转增加了大量的开销.

也就是说，我建议使用预计算查找表.其 idea 如下.我们需要一个按匹配位数、按下一个字节表示当前匹配位数的array.这可以存储在长度为bits * 256的数组中.第256*a + b位的值是一个数字，告诉你如果你之前匹配了a位，b是下一个字节，那么你现在匹配了多少位.

现在，您的逻辑如下所示(忽略强制转换):

matched = 0
for b in bytes:
    matched = lookup[256*matched + int(b)]
    if matched == length_of_needle:
        return True
return False

以下是演示这一 idea 的一些示例代码.请注意，我对位的末尾进行了0填充，以获得偶数个字节.

# Assuming that needle is an array of bits.
def needle_to_lookup (needle):
    ord2bits = []
    for j in range(256):
        bits = []
        k = j
        for _ in range(8):
            bits.append(k % 2)
            k = k // 2
        ord2bits.append(tuple(reversed(bits)))

    lookup = []
    for i in range(len(needle) + 1):
        for bits in ord2bits:
            # Do we successfully keep matching?
            matched = i
            for j in range(8):
                if i + j == len(needle):
                    matched = i+j
                    break
                elif needle[i+j] == bits[j]:
                    matched = i+j
                else:
                    matched = 0
                    break
            if 0 == matched: # Failed to extend for a byte.
                for j in range(8):
                    for k in range(8 - j):
                        if k == len(needle):
                            matched = k
                            break
                        elif needle[k] == bits[j+k]:
                            matched = k+1
                        else:
                            matched = 0
                            break
                    if 0 < matched:
                        break
            lookup.append(matched)
    return lookup

def find_needle(needle, byte_list):
    lookup = needle_to_lookup(needle)
    matched = 0
    for byte in byte_list:
        matched = lookup[256*matched + byte]
        if matched == len(needle):
            return True
    return False
            

print(find_needle([1, 0, 1, 1, 0, 0, 1], bytes([175, 89, 85, 184])))
print(find_needle([1, 1, 1, 0, 1, 1], bytes([175, 89, 85, 184])))