Java（high + low）/ 2が間違っていますが（high + low）>>> 1でないのはなぜですか？

Question

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

---

マイ不審：私はそれは私達が余分なスペースを持っていた場合、オーバーフローが右の数ですが、行っておりませんので、それが負になるように、Javaは、二賛辞を使用するという事実に関係していと思います。あなたがシフトして0でパドルすると、2つの賛辞のために魔法のように修正されます。しかし、私は間違っている可能性があり、ビット単位の脳を持つ人は確認する必要があります。 :)

Answer 1

、(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 

これらを一緒に追加すると、トップビットに「スピル」する可能性があります。符号付き32ビット整数として

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 

• 、それはオーバーフローされ、負反転。したがって、(high + low)/2は、high + lowが負である可能性があるため間違っています。

• 符号なし32ビット整数として、その合計は正しいです。すべてのことが必要なのJavaは符号なし整数をサポートしていません。もちろん、2

ことによってそれを分割することであるので、我々は（符号なし整数として）2で割るする必要が最善のことは、論理右シフト>>>です。

符号なし整数（CやC++など）の言語では、入力が完全な32ビット整数になる可能性があるため、扱いにくくなります。一つの解決策は次のとおりです。low + ((high - low)/2)

---

最後に>>>、>>、と/の違いを列挙する：

• >>>は論理右シフトです。それは、上位ビットをゼロで満たす。
• >>は、算術右シフトです。それは元のトップビットのコピーで上部を埋めます。
• /は部門です。数学的

：

x >>> 1
• 扱い符号なし整数としてx及び2でそれを分割します。それは丸められます。
• x >> 1は符号付き整数としてxを扱い、2で除算します。負の無限大に向かって丸くなります。
• x/2は符号付き整数としてxを扱い、2で除算します。それはゼロに向かってラウンドします。

Answer 2

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

int a = 0x40000000; 
(a + a)/2 == 0xC0000000; 
(a + a) >>> 1 == 0x40000000; 

Answer 3

私はJochブロッホのhttp://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html#!/2006/06/extra-extra-read-all-about-it-nearly.html JDKが同じバグが含まれているために、私が書いたバイナリサーチのバージョン」

ハイとローについてを読むことをお勧めしたい。それは日に報告された最近時9年ほど待たずに誰かの プログラムを破った」