3

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

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

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

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

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

我实现的第三种方式是一种非计算方式，并且是最快的，它使用一个字典，其中包含 ids 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

（这里有一个非常相似的问题：在 Python 中返回最低有效位的索引，但首先，在这种情况下，我知道只有 1 个标记位，其次，我想让它保持纯 Python 解决方案）

4

1 回答 1

6

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

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

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

于 2012-08-05T17:34:20.930 回答