计算一个数字中的设置位数

Question

问题陈述是:

编写一个有效的程序来计算整数二进制表示的1的数量.

我在这里发现了一个关于这个问题的帖子,其中概述了在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总是慢一个百分比.

Answer 2

假设您正在尝试计算n. 在Python 的典型实现中，bin将O(log n)及时计算二进制表示并count遍历字符串，因此导致整体O(log n)复杂性。

但是，请注意，通常，算法的输入参数是输入的“大小”。当您使用整数时，这对应于它们的对数。这就是为什么说当前算法具有线性复杂度（变量为m = log n，复杂度为O(m)）。