二分探索のようなアルゴリズムで 2 つの数値を平均化する必要があるときはいつでも、次のようにします。
int mid = low + ((high - low) / 2);
最近、この投稿で別の方法を見ましたが、理解できません。Javaでこれを行うことができると言われています:
int mid = (low + high) >>> 1;
またはこれをC++で:
int mid = ((unsigned int)low + (unsigned int)high)) >> 1;
C++ バージョンでは、基本的に両方のオペランドが符号なしになるため、シフトを実行すると、符号付きシフトではなく算術シフトが発生します。これらのコードの両方が何をしているのかは理解していますが、オーバーフローの問題はどのように解決されるのでしょうか? high + low
全体の問題は、中間値がオーバーフローする可能性があることだと思いましたか?
編集:
ああ、当たり前。すべての回答が私の質問に正確に答えたわけではありませんが、クリックしたのは@John Zeringueの回答でした。ここで説明してみます。
(high + low)/2
Java での問題は、正確にはhigh + low
オーバーフローではありません (整数は両方とも署名されているため、オーバーフローしますが、すべてのビットはまだそこにあり、情報が失われることはありません)。このように平均を取る際の問題は、除算です。除算は符号付きの値で行われるため、結果は負になります。代わりにシフトを使用すると、2 で除算されますが、符号の代わりにビットが考慮されます (実質的に符号なしとして扱われます)。