計算二進制表示中1的數量 - 右移不起作用？

Question

當問這個問題來計算二進制表示中的1的個數時，我想到的第一個答案是將數字右移並計數最不重要的位

但有一種說法，即當數字是否定的，這種方法會造成無限循環？

我很快就試圖與蟒蛇

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

這是我所期望的，所以有什麼問題，將轉向負數安排進行符號位到正確的？

Answer 1

如果我們談論的是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)) 

Answer 2

這是真的，你會得到一個無限循環，因爲一旦你到-1你不能離開那裏：

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

這聽起來像功課，所以我不會給你一個完整的答案，但看看內置的mod函數。

Answer 3

請參閱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。因此，你會以無限循環結束。