c - 算術オーバーフローを防止する二分探索の論理右シフト

Question

二分探索の実装では、明らかに:

mid = (low + high)/2

オーバーフローを引き起こす可能性があります。私は多くのドキュメント (このような) を読みましたが、次のようにして問題を防ぐことができます。

mid = (low + high) >>> 1 

ただし、これが機能する理由はわかりませんでした。誰でもこれに光を当てることができますか？

Answer 1

C には「論理右シフト」のようなものはありません (>>>演算子はありません)。したがって、おそらく Java について話しているのでしょう。

これが機能するのは、 lowandhighが 0 から 2^31-1 の範囲にあると想定されているためです (ここで話していると仮定しますint)。の可能な最大値はlow+highよりも大きくないため、 (そのようなものが Java に存在する場合2^32-2) で表現できます。unsigned intそのようなことは Java には存在しないので、オーバーフローしました。ただし、論理シフト演算子>>>はそのオペランドを符号なしのように扱うため、期待どおりの結果が得られます。

Answer 2

>>>Java の符号なし右シフト演算子 ( ref ) です。mid、low、およびhighは符号付き整数であるため、 と を加算するとlow負highの値にオーバーフローする可能性があります。>>>この結果の潜在的な負性を無視し、符号なしの数値であるかのように右にシフトします (Java には符号なしの数値はありません)。

C および C++ では、これは

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

（リンク先の記事で明示的に言及されています）。

これは結局同じです

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

おそらく、このようにしたくないことに注意してください。符号なしの値を使用する場合は、符号なしの値に固執し、符号付きと符号なしの間を行ったり来たりしないようにする必要があります。

Answer 3

同じリンクは、Java の >>> を使用する理由を示しており、その理由は (low+high) が「mid」が保持できる最大値を超える可能性があることです。

Programming Pearls Bentley は、同様の行で「m を l と u の平均に設定し、最も近い整数に切り詰める」と述べています。一見、このアサーションは正しいように見えますが、int 変数 low および high の値が大きい場合は失敗します。具体的には、low と high の合計が最大の正の int 値 (231 - 1) より大きい場合に失敗します。合計は負の値にオーバーフローし、値は 2 で割ったときに負のままです。C では、これにより配列インデックスが範囲外になり、予測不能な結果が生じます。

また、C での同等の操作についても述べています。

……

C および C++ (>>> 演算子がない場合) では、次のようにすることができます。

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

したがって、解決策は、その記事を完全に読んで理解することです。

Answer 4

オペレーターで>>>はない他の回答で述べられているように。C

ただし、でのオーバーフローを回避したい場合はC、これを試すことができます:

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