Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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;     } 
like image 680
eagertoLearn Avatar asked Sep 27 '13 19:09

eagertoLearn


People also ask

What is >>> mean in Java?

The >> operator is a signed right shift operator and >>> is an unsigned right shift operator. The left operands value is moved right by the number of bits specified by the right operand.

What is the use of >>> operator?

The unsigned right shift operator ( >>> ) (zero-fill right shift) evaluates the left-hand operand as an unsigned number, and shifts the binary representation of that number by the number of bits, modulo 32, specified by the right-hand operand.

What is the difference between >> vs >>> in Java?

Difference between >> and >>> operator. Both >> and >>> are used to shift the bits towards the right. The difference is that the >> preserve the sign bit while the operator >>> does not preserve the sign bit. To preserve the sign bit, you need to add 0 in the MSB.

What does shift () do in Java?

The shift operator is a java operator that is used to shift bit patterns right or left.


2 Answers

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. 
like image 52
rgettman Avatar answered Sep 30 '22 22:09

rgettman


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.

like image 39
Peter Lawrey Avatar answered Sep 30 '22 23:09

Peter Lawrey