计算二进制表示中1的数量 - 右移无效？

Question

当被问到如何计算一个数字在二进制表示中有多少个1时，我首先想到的方法就是把这个数字向右移动，然后数一下最右边的那一位。

但是有一种说法是，当这个数字是负数时，这种方法会导致无限循环？

我用Python快速试了一下。

>>> a = -16
>>> a >> 1
-8
>>> a >> 1
-8
>>> -8 >> 1
-4
>>>

这是我预期的结果，那么问题出在哪里呢？把负数向右移动会不会把符号位也一起移动到右边？

Answer 1

请查看 这个链接：向右移动就相当于除法。然后再看看 这个链接：整数除法会自动对结果进行向下取整，所以 -1 / 2 = -1，因为 floor(-0.5) = -1。不管你从哪个数字开始，最后都会得到 -1。因此，这样会导致一个无限循环。

Answer 2

没错，你会遇到一个无限循环的问题，因为一旦你到了 -1，就无法再出来了：

>>> a = -1
>>> a >> 1
-1

这听起来像是作业，所以我不会给你完整的答案，但你可以看看内置的 mod 函数。

Answer 3

如果我们在谈论Python的无限精度整数，那么任何负数都有无穷多个1！所以不管是用什么方式填充符号（这在C语言中也会出现），计算负数的位数是没有意义的，除非你有一个固定的位数。

对于32位或64位的整数，只需要按位移位这么多次，然后停止就可以了。

下面是32位整数-4的位表示。

>>> n = -4
>>> for bit in reversed([ (n>>shift)&1 for shift in range(32) ]):
...    print bit,
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0

所以总结一下，就是

sum( (n>>shift)&1 for shift in range(32) )