如何不转换为二进制检查汉明重量？

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

你无法让这个计算变得更简单。它的复杂度是O(n)，也就是位数的数量，或者像用&运算符的技巧所示，是O(n)，也就是设置为1的位数的数量；但除非你用的数字是某种特殊情况，否则后者平均来说应该是n/2，所以这两种O(n)的情况其实是一样的。

而查找表的技巧，其实对计算复杂度没有什么帮助；它只是用空间换取时间，但并没有改变根本的逻辑，那就是你必须以某种方式检查每一位，而这没有捷径可走。你无法不检查每一位，就逻辑上来说，无法回答关于数字位的问题。

现在，我想我有点马虎，因为这些例子实际上是O(n^2)，因为在Python中你必须一次性检查整个数字。比如说，一个100字节的Python长整型，进行加法、&运算或除法时，至少会检查每个字节一次，这个过程会不断重复，直到数字减到零（在上面提到的方案中），所以这些操作实际上是O(n^2)。我不太确定Python是否能实现真正的O(n)解决方案。

总之：如果你真的是在问关于计算复杂度的问题，特别是指大O分析，那就是你的答案。:-)

Answer 2

我不是一个Python程序员，但希望这些内容能让你理解。

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

return c

虽然有点难懂，但它的主要优点是速度快和简单。这个while循环只会针对n中每个被设置为1的位执行一次。

Answer 3

在我看来，一个不错的方法是使用查找表——也就是创建一个字典，把字节转换成1的数量（你可以用你发的代码来生成这个字典，只需要运行一次就可以了），然后可以用类似下面的方式：

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

我觉得这样在占用空间和运行时间之间是个比较好的折中方案。