Re:Nearly All Binary Searches and Mergesorts Are Broken (2006)
by psyklic on Saturday July 23, 2016 @01:41AM
(#12148508)
low and high are assumed to be positive and at most 2^31 - 1. So, there is a zeroed high bit in each which, for a signed int, is reserved to indicate negation.
When low and hi are summed together, the high bit of the result might be set. For a signed int, this would be an accidental overflow and would be falsely interpreted as a negative number. However, if you interpret the result as an unsigned int, it would be the correct sum.
The Java logical shift operator >>> does not retain the sign when shifting. So, it will always shift a 0 into the high bit, making the result a positive signed int.
In most C implementations, >> is an arithmetic shift, which would retain the sign in the result. So in C, we would need to cast low and high as unsigned first; otherwise, the high bit will be retained rather than shifted.
At the risk of sounding stupid, I had a question about the following solution:
I understand that right shift is like dividing by 2, just like in decimal right shifting the digits is like dividing by 10 (654/10 = 065). But why can we just ignore the low + high overflow issue? Is it because the overflow will be stored in the two's complement bit and right shift doesn't care about what that bit represents? If unsigned ints were used instead, I suppose that trick wouldn't work?