CODEWITHSUNDEEP
javabinary
Zanko
Zanko

Reputation: 4694

Overflow, or not, with >>> operator

I have always been using int mid = low + ((high - low) / 2); to calculate mid point as this prevent potential overflow. This makes sense because the (high - low) / 2 ensures there is no overflow. However recently I just found out a faster way. This is by doing int mid = (low + high) >>> 1;.

Apparently this does not cause overflow as well. Can somebody explain why? This is very similar to int mid = (low + high) / 2 where (low + high) causes overflow.

 System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) / 2); // -1
 System.out.println((Integer.MAX_VALUE + Integer.MAX_VALUE) >>> 1); //2147483647

 System.out.println((Integer.MAX_VALUE + (Integer.MAX_VALUE - Integer.MAX_VALUE) / 2)); //2147483647

Upvotes: 1

Views: 119

Answers (2)

slim
slim

Reputation: 41223

This defends against overflow by effectively doubling the maximum number you can represent. Unlike >>, >>> does not treat the sign bit as special, so as far as this operation is concerned, you have all 32 bits to represent the numbers.

To make examples easier, let's imagine a 3 byte signed type, using two's-complement, as Java does for its integer types.

0b000 = 0
0b001 = 1
0b010 = 2
0b011 = 3     // MAX
0b100 = -4    // MIN
0b101 = -3
0b110 = -2
0b111 = -1

In two's-complement, if the leftmost bit is zero, interpret the number as a positive. If the leftmost bit is one, it's a negative; invert the bits and add one to get the magnitude.

  0b101 
= -(0b010 + 1) 
= -(2 + 1) 
= -3

... and has the desirable property that incrementing 011 to 100 overflows in as sensible way as there can be -- MAX to MIN, and decrementing 000 to 111 gives you -1.

Now, if we add 3 + 2 in this scheme, we overflow into the negatives:

0b011 + 0b010 = 0b101

This would translate to 5 (correct) if we interpret it as an unsigned 3-bit integer. But since Java interprets integers as two's-complement, it translates to -3.

-3 / 2 gives -1 -- not the answer we want.

-3 >>> 1 gives 0b101 >>> 1 gives 0b010, which is 2, the answer we want.

So here we have used >>> 1 as "divide by two, treating the original number as an unsigned integer". Of course you can only use this to divide by powers of two.

In Java 8 there are a number of new methods in java.lang.Integer and java.lang.Long for treating numbers as unsigned. One is divideUnsigned() which can be used to divide by an arbitrary number:

Returns the unsigned quotient of dividing the first argument by the second where each argument and the result is interpreted as an unsigned value.

It may be helpful to future readers of your code to use this in preference to >>>.

By working with ints using unsigned-safe methods, you can work with numbers larger than Integer.MAX_VALUE -- 2^31 -1. But you can still overflow if you exceed 2^32 -1.

The largest a Java array or List can be is Integer.MAX_VALUE, so for array or List indices, (low + high) >>> 1 or Integer.divideUnsigned( low + high, 2) are safe.

Upvotes: 3

Durandal
Durandal

Reputation: 20059

Depends on what you deem "overflow proof". The >>> operator itself has nothing to do with overflow, its the expression "low + high" that can overflow.

In practice however, low/high will be either list or array indices (read: positive ints), and that makes all the difference.

While adding low + high can exceed Integer.MAX_VALUE (which is an overflow), ">>> 1" treats the argument as unsigned - thus the bit that possibly overflowed and caused a sign flip is recovered correctly by shifting usigned, bringing the result back into the range of a signed int.

Upvotes: 1

Related Questions