python - 计算其二进制表示中 1 的数量——右移不起作用？

Question

当被问到计算二进制表示中 1 的个数时，我想到的第一个答案是将数字右移并计算最不重要的位

但是有一种说法，当数字为负数时，这种方法会导致死循环吗？

我用python快速尝试

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

这是我所期望的，那么问题是什么，将负数移动会导致符号位向右转移？

Answer 1

的确，你会得到一个无限循环，因为一旦你到达-1你就无法离开那里：

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

这听起来像功课，所以我不会给你一个完整的答案，但看看内置的mod功能。

Answer 2

请参阅http://docs.python.org/2/reference/expressions.html#shifting-operations：向右移动等同于除法。然后检查http://docs.python.org/2/reference/expressions.html#binary-arithmetic-operations：整数除法隐含地应用于floor结果，因此，无论您-1 / 2 = -1从floor(-0.5) = -1哪个数字开始，您最终都会达到-1。因此，您最终会陷入无限循环。

Answer 3

如果我们谈论的是 python 的无限精度整数，那么任何负数都有无限个 1！因此，不管符号填充（您也将在 C 中得到），除了固定位长度外，以负数计算位是没有意义的。

对于 32 位或 64 位 int，只需移动多次并停止。

这是 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) )