python - 在纯 python 中获取标记位索引

Question

我在这里涉及两个问题:一个是“如何”，第二个是“这个很棒的解决方案听起来不错吗？”
事情是这样的:我有一个具有 int 值的对象，它存储所有使用该对象的人的 ID。这是使用标记技术完成的(人员 ID 为 0-10)。

我遇到了一种情况，如果这个值只用一个 id 标记，我想获取这个 id。

第一次测试我使用了value & (value-1)这很好，但至于第二件事，我开始想知道什么是最好的方法(我想知道的原因是因为这种计算在关键位置每秒至少发生 300 次)。

所以我想到的第一种方法是使用 math.log(x,2) ，但我对这个解决方案感到有点不舒服，因为它涉及一个值的“硬”数学，而不是非常简单的位操作，我觉得我遗漏了一些东西。

我想到的第二种方法是计算 value<<1直到它达到 1，但正如您在基准测试中看到的那样，它变得更糟了。

我实现的第三种方式是一种非计算方式，而且速度最快，它使用了一个字典，其中包含 id 0-10 的所有可能值。

就像我之前说的:在纯 python 中是否有“正确”的方法？
基于字典的解决方案是“合法”解决方案吗？ (可读性/任何其他原因为什么不这样做？)

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)

输出:

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

(这里有一个非常相似的问题:return index of least significant bit in Python，但首先，在这种情况下，我知道只有 1 个标记位，其次，我想将其保留为纯 Python 解决方案)

Answer 1

如果您使用的是 Python 2.7 或 3.1 及更高版本，则可以使用 bit_length整数的方法。它返回表示整数所需的位数，即比最高有效位的索引多一位:

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

这可能是最符合 Python 风格的解决方案，因为它是标准库的一部分。如果您发现 dict 性能更好并且这是一个性能瓶颈，我认为没有理由不使用它。