14

如何在不实际转换和计数的情况下获得数字二进制表示中“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
4

8 回答 8

12

我不是 python 程序员，但希望它足以让你遵循。

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

return c

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

于 2009-05-09T19:05:58.297 回答
7

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

当然，查找表技巧实际上对计算复杂度没有任何作用。它只是用空间来支付时间，但不会改变基本的经济学原理，即你必须以某种方式检查每一位，并且没有办法解决这个问题。从逻辑上讲，如果不检查每个位，您就无法回答有关数字中的位的问题。

现在，我想我有点草率，因为其中许多示例实际上都是 O(n^2)，因为在 Python 中，您必须一次检查整数，因此使用 Python 长整数，例如 100 字节, + 或 & 或 / 操作将至少查看每个字节一次，并且会一遍又一遍地发生，直到数字减少到零（在上面概述的方案中），所以这些，再次，真的是 O( n^2) 操作。我不确定 Python 是否会在这里允许真正的 O(n) 解决方案。

无论如何：如果您真的在询问计算复杂性，这特别是指大 O 分析，这就是您的答案。:-)

于 2009-05-09T20:12:20.213 回答
5

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

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

我相信这是空间和运行时间之间相当好的权衡。

于 2009-05-09T19:46:52.630 回答
4

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

sum( [x&(1<<i)>0 for i in range(32)] )
于 2009-05-09T20:03:13.340 回答
1

如果您真的关心速度，请用 C 编写代码（请参阅这个问题了解如何），并使用类似ctypes的东西与 C 实现接口。

于 2009-05-09T19:12:23.477 回答
1

这里：

def bitCount(int_no):

    c = 0
    while(int_no):
        int_no &= (int_no - 1)
        c += 1
    return c

这可能是一种古老而有效的方法……最初是用 C 实现的（Algo 有一个我不记得的名字）。它对我有用，希望对其他人有用

于 2016-04-11T17:47:35.523 回答
1

https://en.wikipedia.org/wiki/Hamming_weight。

O(log(n)) 的解决方案，n 是位长

m1  = 0x5555555555555555 #binary: 0101...
m2  = 0x3333333333333333 #binary: 00110011..
m4  = 0x0f0f0f0f0f0f0f0f #binary:  4 zeros,  4 ones ...
m8  = 0x00ff00ff00ff00ff #binary:  8 zeros,  8 ones ...
m16 = 0x0000ffff0000ffff #binary: 16 zeros, 16 ones ...
m32 = 0x00000000ffffffff #binary: 32 zeros, 32 ones
h01 = 0x0101010101010101 #the sum of 256 to the power of 0,1,2,3...

def hammingWeight(self, x: int) -> int:
    x -= (x>>1)&m1
    x = (x&m2) + ((x>>2)&m2)
    x = (x+(x>>4))&m4
    return ((x*h01)>>56)&0x7f

而在 python 3.10 中，int 类型将有一个 bit_count() 方法

于 2021-02-01T08:31:22.090 回答
0

p= λ n:n 和 1+p(n&(n-1))

这使用了短路和递归，当n大于0时，它切换到计算1+p(n&(n-1))，其中调用p(n&(n-1))等等，当n为0时它返回 0。复杂度为 O(n)，因为它运行二进制文件中存在的数量的次数。

示例：p(9)=1+p(8)=1+1+p(0)=1+1+0=2

于 2016-04-08T15:03:25.387 回答