如何在不转换为二进制的情况下检查汉明重量？

Question

如何在没有实际转换和计数的情况下获得数字的二进制表示中的"1"的数量？

例如

  def number_of_ones(n):
      # do something
      # I want to MAKE this FASTER (computationally less complex).
      c = 0
      while n:
        c += n%2
        n /= 2
      return c


>>> number_of_ones(5)
    2
>>> number_of_ones(4)
    1

Answer 1

我不是一个python程序员,但希望你能够遵循它.

c = 0
while n:
    c += 1
    n &= n - 1

return c

虽然有点模糊,但它的主要优点是速度和简单性.对于n中设置为1的每个位,while循环仅迭代一次.

Answer 2

你不能使这个计算上不那么复杂.它将是O(n)的位数,或者,如同&技巧的答案所示,O(n)的位数设置为1; 但除非您使用的所有数字都是特殊情况,后者平均应为n/2,因此这两个O(n)数字都是相同的.

当然,查找表技巧实际上对计算复杂性没有任何作用; 它只是用空间来支付时间,但没有改变基础经济学,你必须以某种方式检查每一位,而且没有办法解决这个问题.从逻辑上讲,您无法在不检查每个位的情况下回答有关数字位的问题.

现在,我想我有点草率,因为这些例子实际上是O(n ^ 2),因为在Python中你必须一次检查整数,所以使用Python长整数,比方说,100字节,一个+或一个&或一个/操作将至少查看一次每个字节,这将一遍又一遍地发生,直到数字减少到零(在上面概述的方案中),所以这些实际上也是O( n ^ 2)操作.我不确定Python会在这里允许真正的O(n)解决方案.

无论如何:如果你真的在询问计算复杂性,这特别意味着大O分析,那就是你的答案.:-)

Answer 3

如果你想在一行中完成它，你可以使用：

sum( [x&(1<<i)>0 for i in range(32)] )

Answer 4

IMO,一个好的方法是使用一个查找表 - 创建一个字典,将字节转换为1的数字(你可以使用你发布的代码生成它,它只需要运行一次),然后使用一些东西像这样:

def number_of_ones(n):
    sum = 0
    while n != 0:
        sum += lookup_table[n & 0xff]
        n >>= 8
    return sum

我相信这在空间和运行时间之间是一个相当不错的权衡.