CODEWITHSUNDEEP
pythonbit-manipulationbit
Jerfov2
Jerfov2

Reputation: 5504

Python How to get set bit

Say I have a number that in memory looks like this (or similar, I don't know exactly how Python stores numbers):

0000 0000 0000 1000

I want to get what bit is set (Thanks to @muddyfish, I will clarify that these numbers will have only one bit set), in this case 3, because 2^3 = 8. I could just use log2 to achieve this, but this seems like something that could easily be solved by 'bit twiddling' techniques. I could also loop through all the bits like this:

def getSetBit(num):
    if num == 0:
        return -1

    bit = 0
    while num != 1:
        bit += 1
        num >>= 1

    return bit

# getBitSet(0b100000) == 5
# getBitSet(1) == 0

However this to me seems awkward and slower than it should be. If this is the only way to do this, I guess I could live with it, but I would like it if it wasn't.

Upvotes: 2

Views: 5837

Answers (1)

muddyfish
muddyfish

Reputation: 3650

To get the bit number of the highest bit set, you could use

int.bit_length()-1

This is much more efficient then using math.log() or the other function you had posted

EDIT:

As requested, timeit results are posted:

python -m timeit -s 'import math;x=100' 'int(math.log(x,2))'

1000000 loops, best of 3: 0.5 usec per loop

python -m timeit -s 'i = 100' 'i.bit_length()-1'

10000000 loops, best of 3: 0.106 usec per loop

Also, using math.log will yeild inaccurate results for values higher than 2**29.

Upvotes: 5

Related Questions