如何高效获取二进制字符串中的索引

Question

我正在寻找一种有效的方法来确定哪些位是整数的二进制表示形式中的位。

我有一个库（adafruit_mpr121），它返回一个按照以下方式构造的整数：

a = bytearray(2)
b = bytearray(2)
((a[1] << 8) | (a[0])) & 0xFFFF

我可以得到所述整数的字符串二进制表示形式，格式如下：

'{0:0<12b}'.format(bin_int)

，我可能可以找到带有

re.finditer()

的索引，但我认为有一些更有效的方法，无需遍历所有这些操作。这个完整的操作大约需要我在设备扫描之间睡觉的时间，所以一点也不太好：

>>> timeit.timeit('[m.start() for m in re.finditer("1", "{0:0<12b}".format(((a[1] << 8) | (a[0])) & 0xFFFF))]', setup='import re; a = bytearray(2); a[0]=16; a[1]=5', number=10000)

0.026143900002352893

有谁知道有什么方法可以更快吗？

Answer 1

在数字领域而不是字符串中进行操作可能更有效。我发现这个函数比正则表达式方法快大约 50%。

方法是将数字左移位长-1，以确定最高有效位（MSB）是否被设置。如果已设置，则计算索引并按 MSB 表示的 2 的幂递减。

def compute_indexes(n):
    orig_num_bits = n.bit_length() - 1
    indexes = []
    for num_bits in range(orig_num_bits, 0, -1):
        if (n >> num_bits) == 1:
            indexes.append(orig_num_bits - num_bits)
            n -= (1 << num_bits)
    return indexes