30

オーバーフローの修正を理解して>>>います。2 つの大きな正の long を追加すると、負の数になる可能性があります。このビットごとのシフトがオーバーフローの問題を魔法のように修正する方法を誰かが説明できますか? そして、それはどのように違うの>>ですか？

私の疑惑: Java が 2 の補数を使用しているため、余分なスペースがあればオーバーフローは適切な数ですが、そうでない場合は負になるという事実に関係していると思います。したがって、シフトしてゼロでパディングすると、2 の補数により魔法のように修正されます。しかし、私は間違っている可能性があり、ビット単位の頭脳を持つ誰かが確認する必要があります. :)

4

3 に答える 3

54

要するに、(high + low) >>> 1未使用の符号ビットを使用して、負でない数値の正しい平均を実行するトリックです。

highとlowが両方とも非負であるという仮定の下で、最上位ビット (符号ビット) がゼロであることは確実です。

したがって、highとlowは実際には 31 ビット整数です。

high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824
low  = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

それらを一緒に追加すると、トップビットに「こぼれる」場合があります。

high + low =       1000 0000 0000 0000 0000 0000 0000 0000
           =  2147483648 as unsigned 32-bit integer
           = -2147483648 as signed   32-bit integer

(high + low) / 2   = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824
(high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824

  • 符号付き 32 ビット整数として、オーバーフローし、反転します。したがって、負になる可能性がある(high + low) / 2ため、間違っています。high + low

  • 符号なし 32 ビット整数として、合計は正しいです。必要なのは、それを 2 で割ることだけです。

もちろん、Java は符号なし整数をサポートしていないため、(符号なし整数として) 2 で除算する必要がある最善の方法は、論理右シフト>>>です。

符号なし整数を使用する言語 (C や C++ など) では、入力が完全な 32 ビット整数になる可能性があるため、より複雑になります。1つの解決策は次のとおりです。low + ((high - low) / 2)

>>>最後に、 、>>、およびの違いを列挙します/。

  • >>>論理右シフトです。上位ビットをゼロで埋めます。
  • >>算術右シフトです。元のトップビットのコピーでアッパーを埋めます。
  • /分割です。

数学的に：

  • x >>> 1x符号なし整数として扱い、それを 2 で割ります。切り捨てます。
  • x >> 1符号付き整数として扱いx、それを 2 で除算します。負の無限大に向かって丸めます。
  • x / 2符号付き整数として扱いx、それを 2 で除算します。ゼロに向かって丸めます。
于 2012-12-09T06:37:42.513 に答える
11

最上位ビットを符号で埋めるのではなく、ゼロで埋めます。

int a = 0x40000000;
(a + a)  /  2 == 0xC0000000;
(a + a) >>> 1 == 0x40000000;
于 2012-12-09T06:25:21.860 に答える