get the flagged bit index in pure python

Question

i involve here 2 questions: one is for 'how', and second is for 'is this great solution sounds ok?'
the thing is this: i have an object with int value that stores all the persons' ids that used that object. it's done using a flagging technique (person id is 0-10).

i got to a situation where in case this value is flagged with only one id, i want to get this id.

for the first test i used value & (value-1) which is nice, but as for the second thing, i started to wonder what's the best way to do it (the reason i wonder about it is because this calculation happens at least 300 times in a second in a critical place).

so the 1st way i thought about is using math.log(x,2), but i feel a little uncomfortable with this solution since it involves "hard" math on a value, instead of very simple bits operation, and i feel like i'm missing something.

the 2nd way i thought about is to count value<<1 until it reaches 1, but it as you could see in the benchmark test, it was just worse.

the 3rd way i was implemented is a non-calc way, and was the fastest, and it's using a dictionary with all the possible values for ids 0-10.

so like i said before: is there a 'right' way for doing it in pure python?
is a dictionary-based solution is a "legitimate" solution? (readability/any-other-reason-why-not-to?)

import math
import time

def find_bit_using_loop(num,_):
    c=0
    while num!=1:
        c+=1
        num=num>>1
    return c

def find_bit_using_dict(num,_):
    return options[num]

def get_bit_idx(num, func):
    t=time.time()
    for i in xrange(100000):
        a=func(num,2)
    t=time.time()-t
    #print a
    return t

options={}
for i in xrange(20):
    options[1<<i]=i

num=256
print "time using log:", get_bit_idx(num, math.log)
print "time using loop:", get_bit_idx(num, find_bit_using_loop)
print "time using dict:", get_bit_idx(num, find_bit_using_dict)

output:

time using log: 0.0450000762939
time using loop: 0.156999826431
time using dict: 0.0199999809265

(there's a very similar question here: return index of least significant bit in Python , but first, in this case i know there's only 1 flagged bit, and second, i want to keep it a pure python solution)

Why do you want to use only one value to store a set of numbers? — murgatroid99, Aug 05 '12 at 17:13
because the flagging/flag-testing actions are both in the most intensive areas in the code, and the most efficient way i found for that is the bitwise operations. — RoeeK, Aug 05 '12 at 17:22
OK. Why are you particularly asking about the legitimacy of the `dict` solution? It seems that it is the most readable, most Pythonic, and fastest, just from seeing what you have written there. Is there some reason *you* think it is not a "legitimate" solution? — murgatroid99, Aug 05 '12 at 17:28
since i'm not considering myself as a python-expert, a dict-based solution feels to me like doing something wrong. i'm still in a level where i need to validate "strange" solutions since now it might be ok, but i see how easily it could become a very funny joke — RoeeK, Aug 05 '12 at 17:31

score 6 · Accepted Answer · answered Aug 05 '12 at 17:34

If you are using Python 2.7 or 3.1 and above, you can use the bit_length method on integers. It returns the number of bits necessary to represent the integer, i.e. one more than the index of the most significant bit:

>>> (1).bit_length()
1
>>> (4).bit_length()
3
>>> (32).bit_length()
6

This is probably the most Pythonic solution as it's part of the standard library. If you find that dict performs better and this is a performance bottleneck, I see no reason not to use it though.

get the flagged bit index in pure python

1 Answers1