>>>演算子を使用してオーバーフローするかどうか

Question

これは潜在的なオーバーフローを防ぐために、常にint mid = low + ((high - low)/2);を使用していました。これは、(high - low)/2がオーバーフローがないことを保証するため意味をなさない。しかし、最近私はちょうどより速い方法を見つけました。これはint mid = (low + high) >>> 1;です。

明らかに、これもオーバーフローを引き起こしません。なぜ誰かが説明できますか？これはint mid = (low + high)/2と非常によく似ていますが、(low + high)がオーバーフローを引き起こします。

System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE)/2); // -1 
System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) >>> 1); //2147483647 

System.out.println((Integer.MAX_VALUE + (Integer.MAX_VALUE - Integer.MAX_VALUE)/2)); //2147483647 

Answer 1

これは、表現できる最大数を効果的に2倍にすることによってオーバーフローを防ぎます。 >>とは異なり、>>>は、符号ビットを特殊なものとして扱いません。したがって、この操作に関する限り、すべての32ビットで数値を表します。

例を簡単にするために、Javaがその整数型に対して行うように、2の補数を使用して3バイトの符号付き型を想像してみましょう。

0b000 = 0 
0b001 = 1 
0b010 = 2 
0b011 = 3  // MAX 
0b100 = -4 // MIN 
0b101 = -3 
0b110 = -2 
0b111 = -1 

2の補数では、左端のビットがゼロの場合、その数値を正と解釈します。左端のビットが1の場合、負のビットです。ビットを反転し、1を加えて大きさを得る。 111へ000はあなたに-1を与えるMAXMINに、とデクリメント -

0b101 
= -(0b010 + 1) 
= -(2 + 1) 
= -3 

...とが可能な限り賢明な方法で 011 100へのオーバーフローをインクリメント望ましい特性を有しています。私たちは、この方式では3 + 2を追加した場合

は今、私たちは、ネガにオーバーフロー：

0b011 + 0b010 = 0b101 

我々は符号なしの3ビット整数として解釈場合、これは（修正）5に変換します。しかし、Javaは整数を2の補数として解釈するので、-3に変換されます。

-3/2は-1を返します。私たちが望む答えはありません。

-3 >>> 1が0b101 >>> 1の場合、0b010となります。答えは2です。

ここでは、>>> 1を「2で除算し、元の数値を符号なし整数として扱う」として使用しています。もちろん、これを使用して2の累乗で除算することはできます。

Java 8では、数値を符号なしとして扱うために、java.lang.Integerとjava.lang.Longには多くの新しいメソッドがあります。一つは、任意の数で分割するために使用することができるdivideUnsigned()ある：

各引数と結果は符号なしの値として解釈されている第二することにより、第1引数を分割する符号なしの商を返します。

コードの読者が>>>より優先して使用すると便利です。

符号なし安全なメソッドを使用してintを操作すると、Integer.MAX_VALUE-2^31 -1より大きい数値を扱うことができます。しかし、2^32 -1を超えると、オーバーフローする可能性があります。

Java配列またはListの最大サイズはInteger.MAX_VALUEであるため、配列インデックスまたはリストインデックスの場合、(low + high) >>> 1またはInteger.divideUnsigned(low + high, 2)は安全です。

Answer 2

"オーバーフロープルーフ"とみなす内容によって異なります。 >>>演算子自体はオーバーフローとは関係がありません。オーバーフローする可能性のある "low + high"という表現です。

しかし、実際には、low/highはリストまたは配列インデックス（読み取り：正の整数）のいずれかになり、それによってすべての違いが生じます。

"0"を追加するとInteger.MAX_VALUE（オーバーフロー）を超えることがありますが、 ">>> 1"はその引数を符号なしとして扱います。したがって、オーバーフローして符号フリップを引き起こしたビットは、結果を符号付きintの範囲に戻します。