二つの数

Question

の安全な平均の説明私は、バイナリサーチのようなアルゴリズムのための2つの数値を平均化する必要があるたびに、私はいつもこのような何か：

int mid = low + ((high - low)/2); 

を私は最近this postでそれを行うための別の方法を見て、私はそれを理解していません。それはあなたがJavaでこれを行うことができます言う：

C++で

int mid = (low + high) >>> 1; 

またはこの：

int mid = ((unsigned int)low + (unsigned int)high)) >> 1; 

C++バージョンは、本質的にその代わりに、署名の算術シフトでシフト結果をやって、両方のオペランドが符号なしになりますシフト。これらのコードの両方が何をしているのか理解していますが、どのようにオーバーフローの問題を解決しますか？全体の問題は、中間値high + lowがオーバーフローする可能性があると私は考えましたか？

編集：

ああ、当たり前。すべての答えが正確に私の質問に答えなかったが、それはそれをクリックした@ジョンZeringueの答えだった。私はここで説明しようとします。

Javaの(high + low)/2の問題は、あくまでもhigh + lowのオーバーフローです（整数が両方とも署名されているのでオーバーフローしますが、すべてのビットはまだ存在し、情報は失われません）。このような平均をとる問題は部門です。部門は署名された値で動作しているため、結果はマイナスになります。代わりにシフトを使用すると、2で除算されますが、符号の代わりにビットを考慮します（事実上、符号なしとして扱います）。

Answer 1

したがって、intではなくbytesを考えてみましょう。唯一の違いは、バイトが8ビットの整数で、intが32ビットであることです。 Javaでは、両方とも常に署名されています。先頭のビットが正（0）か負（1）かを示します。

byte low = Byte.valueOf("01111111", 2); // The maximum byte value 
byte high = low; // This copies low. 

byte sum = low + high; // The bit representation of this is 11111110, which, having a 
         // leading 1, is negative. Consider this the worst case 
         // overflow, since low and high can't be any larger. 

byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow. 

intの場合も同じです。基本的には、このすべての要点は、符号なし整数に符号なしビットシフトを使用すると、最下位ビットを利用して可能な限り大きな値を扱うことができるということです。

Answer 2

Javaではunsigned intは使用できません。オーバフローの場合、低32ビットが考慮され、高位ビットは破棄される。符号なし右シフトは、intをunsigned intとして扱うのに役立ちます。しかし、C++ではオーバーフローは発生しません。

Answer 3

C++バージョンは、オーバーフローの問題を解決するではありません。 /ではなく、shiftを使用して2で割ることで問題を解決するだけです。これは、パフォーマンスの向上に役立つようにコンパイラが自分自身で作成できる最適化です。

一方、積分型が合理的な範囲のインデックスを保持するのに十分な大きさであれば、オーバーフローは実際の問題ではないかもしれません。

Answer 4

あなたがあるあなたが既に使用し、あなたが言った道を、使用して整数オーバーフローから安全である：

int mid = low + ((high - low)/2); 

は、あなたのコンパイラは、それがする必要がある場合は、これを最適化する仕事ですやってみましょう。

Answer 5

C++バージョンには隠しカンニングがあります：lowとhighはintですが、決して否定的なものではありません。 unsigned intにキャストすると、符号ビットが余分な精度のビットになり、1回の加算でオーバーフローできなくなります。

とにかく配列のインデックスがunsignedである必要があります。

他のところで言われたように、i >> 1は、符号なし整数の場合は/2を意味します。

Answer 6

あなたが見たコードは壊れています。負の数値の平均は正しく計算されません。インデックスのように負でない値だけを操作している場合、それは問題ありませんが、一般的な置き換えではありません。あなたがもともと持っている コード、違いhigh - lowは、符号付き整数の範囲をオーバーフローする可能性があるため

int mid = low + ((high - low)/2); 

は、いずれかのオーバーフローから安全ではありません。繰り返しますが、負でない整数でしか動作しない場合は問題ありません。あなたはビットシフトを使用して2で除算を計算するが、二つではない心に留めておくことができます

int mid = (high&low) + (high^low)/2; 

：私たちは、このようなオーバーフローせずに2つの整数の平均を計算することができますA+B = 2*(A&B) + A^Bという事実を利用し

同じ：ビットシフトが常に切り捨てられますが、除算は0に向かってラウンドします。

int mid = (high&low) + ((high^low)>>1);