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