CODEWITHSUNDEEP
javaoverflowaveragebitwise-operators
tnecniv
tnecniv

Reputation: 157

Java, will (low + high) >> 1 overflow?

I know that >> is for signed and >>> is for unsigned

Similar questions that do not answer my question:

Java, will (low + high) >>> 1 overflow?

Safe integer middle value formula

According to the second link, why do they conclude that: avg = (low & high) + ((low ^ high) >> 1); will avoid overflow?

Why can't they just use this instead : (low + high) >> 1?

(This is for binary search in java)

Upvotes: 2

Views: 175

Answers (1)

rgettman
rgettman

Reputation: 178263

Yes, (low + high) >> 1 may overflow if the sum is high enough. As you know, >>> is for unsigned, so that it will always shift in a 0 on the most significant side. This turns out to be very important in case it does overflow.

The trick to using (low + high) even with overflow is that information is still retained. If it does overflow, the maximum possible mathematical sum is still Integer.MAX_VALUE * 2, which would still be representable as an unsigned int, if Java had one. But we can treat the sum as an unsigned int when dividing by 2 by using the unsigned right shift operator, >>>. When bit-shifting to the right by 1, this lets us treat the sum as an unsigned int, "un-overflowing" the int.

Using >> here won't work if the sum overflows, because it will overflow into a negative number and >> will shift in a 1, keeping the value negative. This results in an incorrect average calculation (2 positive numbers whose sum overflows will result in a negative average).

Whether you're using >>> or >>, overflow is a possibility. So both can overflow. But only >>> will handle the case well, properly "un-overflowing" the sum.

The trick

avg = (low & high) + ((low ^ high) >> 1);

is another way calculating the average when the sum may overflow. This avoids the overflow entirely. This is breaking down the sum into 2 parts -- the "carry" bits and the "non-carry" bits.

When working with addition, the bits that are carried over to the next more significant bit are when both bits are set -- low & high. Normally in addition, these bits have to be shifted left, but we're calculating the average of 2 numbers, so we would shift right in the end also. The net result: no shift here.

The bits that aren't carried are either a 1 if the bits are different or a 0 if the bits are the same -- that's where (low ^ high) comes from (XOR). Normally in addition, these bits aren't shifted, but we're calculating the average of 2 numbers, so we would shift right in the end also. This shift shows up as >> 1. The & and ^ operators don't overflow, so >> will work just fine here.

Example: Average of 1100 (12) and 1010 (10)

1100 & 1010 = 1000
1100 ^ 1010 = 0110, 0110 >> 1 = 0011
1000 + 0011 = 1011 (11)

Upvotes: 2

Related Questions