Python中在整数内查找二进制位序列的最优实现方案

我有两个整数，分别命名为haystack和needle，需要检查needle的二进制表示是否出现在haystack的二进制序列中（可选返回首次出现的位置）。

示例 #

haystack = 0b10101111010110010101010101110
needle = 0b1011001 # 出现在位置13
needle = 0b111011 # 未出现

已知无法写出时间复杂度优于O(h)的代码（h为haystack的二进制位数），以下是我当前的实现代码。

现在需要处理的场景是：用固定不变且为奇数的needle，去检查数十亿个随机haystack整数（因此无法通过预处理haystack来优化速度）。

由于查找位置是可选需求，若能写出时间复杂度更优、仅返回布尔值表示是否存在的代码更佳——因为在数十亿次检查中，多数情况为不存在，仅当确认存在时再用现有代码查找位置即可。同时也接受存在假阳性的优秀概率算法。

当前实现代码 #

def find_needle_in_haystack(haystack, needle):
    n = needle.bit_length()  # 计算needle的二进制位数
    mask = (1 << n) - 1  # 创建一个n位全1的掩码
    i = 0
    while haystack != 0:
        x = haystack & mask  # 通过按位与取haystack的前n位
        if x == needle:
            return i
        i += 1
        haystack >>= 1  # 将haystack右移一位，检查下一组连续n位
    return -1  # 未找到匹配的needle

内容的提问来源于stack exchange，提问作者A.A