56

SO post here で重複を見つけるためにこのコードを見つけました。しかし、この行の意味がわかりませんint mid = (low + high) >>> 1;

private static int findDuplicate(int[] array) {
        int low = 0;
        int high = array.length - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            System.out.println(mid);
            int midVal = array[mid];

            if (midVal == mid)
                low = mid + 1;
            else
                high = mid - 1;
        }
        return high;
    }
4

3 に答える 3

116

この>>>演算子は、Java の符号なし右ビット シフト演算子です。2これは、オペランドを右オペランドの累乗、またはここで効果的に除算し2ます。

との違いは>>、>>>負の数をシフトする場合にのみ表示されます。>>演算子は1、最上位ビットが の場合はビットを1シフト>>>し、0関係なく a をシフトします。

アップデート：

1と2147483647( ) を平均しましょうInteger.MAX_VALUE。簡単に計算できます。

(1 + 2147483647) / 2 = 2147483648 / 2 = 1073741824

ここで、 code を使用すると、(low + high) / 2関連するビットが次のようになります。

          1: 00000000 00000000 00000000 00000001
+2147483647: 01111111 11111111 11111111 11111111
================================================
-2147483648: 10000000 00000000 00000000 00000000  // Overflow
/2
================================================
-1073741824: 11000000 00000000 00000000 00000000  // Signed divide, same as >> 1.

に「シフト」しましょう>>>：

          1: 00000000 00000000 00000000 00000001
+2147483647: 01111111 11111111 11111111 11111111
================================================
-2147483648: 10000000 00000000 00000000 00000000  // Overflow
>>> 1
================================================
+1073741824: 01000000 00000000 00000000 00000000  // Unsigned shift right.
于 2013-09-27T19:44:22.067 に答える
57

の意義

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

は; 符号なしシフトを使用することで、負の数になるオーバーフローを回避します。Java は値をサポートしていないため、これが必要unsigned intです。(ところでchar、署名されていません)

これを書く伝統的な方法は

int mid = (low + high) / 2; // don't do this

ただし、これは合計が大きくなるとオーバーフローする可能性があり、中間で負の数が得られます。

例えば

int high = 2100000000;
int low = 2000000000;
System.out.println("mid using >>> 1 = " + ((low + high) >>> 1));
System.out.println("mid using / 2   = " + ((low + high) / 2));

版画

mid using >>> 1 = 2050000000
mid using / 2   = -97483648

明らかに 2 番目の結果は正しくありません。

于 2013-09-27T19:47:07.893 に答える
7

そのビット単位の演算子..ビット値で動作します。A が 60 を保持する場合、A>>>2 は 15 (ビット値 0000 1111) を与えるとします。

その実際の名前は「Shift Zero right Operator」です。ここで、左オペランドの値は、右オペランドによって指定されたビット数 (この場合は 2) だけ右に移動され、シフトされた値はゼロ (0000) で埋められます。

于 2013-09-27T19:50:31.827 に答える