python - 计算数字中设置位的数量

Question

问题陈述是:

编写一个高效的程序来计算整数二进制表示中 1 的个数。

我找到了关于这个问题的帖子 here其中概述了以 log(n) 时间运行的多个解决方案，包括 Brian Kernigan 的算法和 gcc __builtin_popcount() 方法。

一个没有提到的解决方案是 python 方法:bin(n).count("1") 这也达到了同样的效果。这个方法是否也运行了 log n 次？

Answer 1

您正在将整数转换为字符串，这意味着它必须生成 N 个 '0' 和 '1' 字符。然后您使用 str.count()，它必须访问字符串中的每个字符 以计算 '1' 个字符。

总而言之，您有一个 O(N) 算法，具有相对较高的恒定成本。

请注意，这与您链接到的代码的复杂性相同；整数 n 有 log(n) 位，但算法仍然需要执行 N = log(n) 步来计算位数。因此，bin(n).count('1') 算法是等效的，但慢，因为首先生成字符串的成本很高。

以表格为代价，您可以转向处理整数每字节:

table = [0]
while len(table) < 256:
    table += [t + 1 for t in table]

length = sum(map(table.__getitem__, n.to_bytes(n.bit_length() // 8 + 1, 'little')))

但是，因为 Python 需要生成一系列新对象(一个 bytes 对象和几个整数)，所以此方法的速度永远无法击败 bin(n).count( '1') 方法:

>>> from random import choice
>>> import timeit
>>> table = [0]
>>> while len(table) < 256:
...     table += [t + 1 for t in table]
...
>>> def perbyte(n): return sum(map(table.__getitem__, n.to_bytes(n.bit_length() // 8 + 1, 'little')))
...
>>> def strcount(n): return bin(n).count('1')
...
>>> n = int(''.join([choice('01') for _ in range(2 ** 16)]))
>>> for f in (strcount, perbyte):
...     print(f.__name__, timeit.timeit('f(n)', 'from __main__ import f, n', number=1000))
...
strcount 1.11822146497434
perbyte 1.4401431040023454

无论测试数的位长如何，perbyte 总是慢一个百分比。