10

二分探索のようなアルゴリズムで 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)/2Java での問題は、正確にはhigh + lowオーバーフローではありません (整数は両方とも署名されているため、オーバーフローしますが、すべてのビットはまだそこにあり、情報が失われることはありません)。このように平均を取る際の問題は、除算です。除算は符号付きの値で行われるため、結果は負になります。代わりにシフトを使用すると、2 で除算されますが、符号の代わりにビットが考慮されます (実質的に符号なしとして扱われます)。

4

7 に答える 7

12

あなたが見たコードは壊れています: 負の数の平均を正しく計算していません. インデックスなどの非負の値のみを操作している場合は問題ありませんが、一般的な代替手段ではありません。元々持っているコード、

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

high - low差が符号付き整数の範囲をオーバーフローする可能性があるため、オーバーフローからも安全ではありません。繰り返しますが、負でない整数のみを扱う場合は問題ありません。

A+B = 2*(A&B) + A^B次のように、オーバーフローなしで 2 つの整数の平均を計算できるという事実を使用します。

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

ビット シフトを使用して 2 による除算を計算できますが、この 2 つは同じではないことに注意してください。除算は 0 に向かって丸められますが、ビット シフトは常に切り捨てられます。

int mid = (high&low) + ((high^low)>>1);
于 2013-10-01T08:01:12.677 に答える
7

int の代わりにバイトを考えてみましょう。唯一の違いは、int は 32 ビットであるのに対し、byte は 8 ビットの整数であることです。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 の場合も同じです。基本的に、これらすべての要点は、符号付き整数で符号なしビットシフトを使用すると、先頭ビットを活用して、可能な限り低い値と高い値を処理できるということです。

于 2013-10-01T01:21:33.427 に答える
1

C++ バージョンでは、オーバーフローの問題は解決されません。これは、 の代わりに shift を使用して 2 で除算するという問題を解決するだけ/です。これは、パフォーマンスが向上する場合にコンパイラが実行できる最適化です。

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

于 2013-10-01T01:13:15.370 に答える
0

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

于 2013-10-01T01:13:00.517 に答える
0

すでに使用していると言った方法を使用することで、整数オーバーフローから安全です。

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

必要に応じて、これを最適化するのはコンパイラーに任せてください。

于 2013-10-01T01:16:21.140 に答える