Thursday, March 19, 2009

Interesting Blog by Joshua Bloch

I have been reading an interesting blog by Joshua Bloch, Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

The following solution can be found in latest version of JDK

int mid = (low + high) >>> 1;

The first thing which comes across my mind is that, (low + high) will cause sign overflow too. However, the comment from the following reader clears out my mind.

">>>" is the unsigned right shift operator. So if I'm not mistaken (low + high) is stored in unsigned int and then shifted one to the right dropping remainder leaving a division by 2 with no remainder returned as a signed int. So it does work.

Very cool, isn't it?

No comments: