what does ">>>" mean in java? [duplicate]

Question

This question already has answers here:

Difference between >>> and >> (7 answers)

Java >>> Operator [duplicate] (3 answers)

Closed 8 years ago.

I found this code to find duplicates in SO post here. but I dont understand what this line means 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;
    }

Answer 1

The >>> operator is the unsigned right bit-shift operator in Java. It effectively divides the operand by 2 to the power of the right operand, or just 2 here.

The difference between >> and >>> would only show up when shifting negative numbers. The >> operator shifts a 1 bit into the most significant bit if it was a 1, and the >>> shifts in a 0 regardless.

UPDATE:

Let's average 1 and 2147483647 (Integer.MAX_VALUE). We can do the math easily:

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

Now, with the code (low + high) / 2, these are the bits involved:

          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.

Let's make the "shift" to >>>:

          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.

Answer 2

The significance of

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

is; by using the unsigned shift, it avoids overflows which result in a negative number. This is needed as Java doesn't support unsigned int values. (BTW char is unsigned)

The traditional way to write this was

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

however this could overflow for larger sums and you get a negative number for the mid.

e.g.

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

prints

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

clearly the second result is incorrect.

Answer 3

its a bitwise operator .. It works on the bit value . Suppose if A holds 60 then A>>>2 will give 15 (bit value 0000 1111)

Its actual name is "Shift Zero right Operator" here the left operands value is moved right by the number of bits specified (2 in this case) by the right operand and shifted values are filled up with zeros(0000).