2

I'm using bitsets and want to iterate over the set bits quickly, and without needing to know the max set bit ahead of time. Using this trick, it seems like we can do this without scanning the 0s in the middle. But the linked trick produces set bits as bitsets, not as integers (e.g. the 0th set bit is produced as 0b1, not 0).

Is there a fast bit trick to calculate log2(x) when I know x will be an exact power of 2 (e.g. as in the above case)?

What have I tried

Simplest version, using the standard library and with bits(n) being the linked code:

def bits(n):
    while n:
        b = n & (~n+1)
        yield b
        n ^= b

from math import log2
   
for b in bits(109):
    print(int(log2(b)))

0
2
3
5
6
MikeRand
  • 4,788
  • 9
  • 41
  • 70

1 Answers1

7

Try:

log2 = b.bit_length() - 1

- 1 because 2ⁿ requires n+1 bits.

Shradha
  • 2,232
  • 1
  • 14
  • 26
  • Thanks. The original reason I discarded this one was because of the conversion to binary and `lstrip` (at least in the "Equivalent to" code), but I should profile. – MikeRand Jan 12 '21 at 18:41