69

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;
    }
Community
  • 1
  • 1
eagertoLearn
  • 9,772
  • 23
  • 80
  • 122

3 Answers3

137

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.
rgettman
  • 176,041
  • 30
  • 275
  • 357
  • 2
    @can you illustrate with an example please. that would be very helpful – eagertoLearn Sep 27 '13 at 20:11
  • 1
    Thanks for the great illustration. but in this case `(low+high)/2` and `low + high >>> 1`, how are they equivalent? – eagertoLearn Sep 27 '13 at 21:05
  • 3
    In Java, they aren't equivalent in the case of overflow, as I have illustrated. – rgettman Sep 27 '13 at 21:09
  • 1
    when the overflow occurs, with the unsigned right bit-shift operator, it technically divides by 2 and negates the sign? – eagertoLearn Sep 27 '13 at 21:09
  • 2
    Yes, the `>>>` treats the value as unsigned. If the value was unsigned, then no overflow would have occurred. When shifted, the value is no longer over the maximum `int` value and it can be interpreted correctly as a signed value again. – rgettman Sep 27 '13 at 21:12
71

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.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
8

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).

Subhranshu
  • 174
  • 4