what does ">>>" mean in java?
JavaArraysPrimitiveJava Problem Overview
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;
}
Java Solutions
Solution 1 - Java
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.
Solution 2 - Java
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.
Solution 3 - Java
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).