How to efficiently get indexes of ones in a binary string

Question

I'm looking for an efficient way of determining which bits are ones in a binary representation of an integer.

I have a library (adafruit_mpr121) that returns an integer that is constructed along this lines:

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

I can get string binary representation of said integer with format like this: '{0:0<12b}'.format(bin_int) and I can probably find indexes with re.finditer() but I would think there's some more efficient way without walking through all those operaions. This full operation takes around how long I am sleepig between device skans, so not so good at all:

>>> 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

Does anyone know of any way that would be faster?

Answer 1

Operating in the realm of numbers, rather than strings may be more efficient. I found this function to be approximately 50% faster than the regex approach.

The method is to left-shift the number by its bitlength - 1 to determine whether the most significant bit (MSB) is set. If it is set, compute the index and decrement by the power of two represented by the MSB.

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