Fast average without division

Question

I have a binary search loop which gets hit many times in the execution path.

A profiler shows that the division part of the search (finding the middle index given the high and low indices of the search range) is actually the most costly part of the search, by a factor of about 4.

(I think) it is not critical for efficient binary search to find the exact middle value, just a value near the middle which does not have bias in either direction.

Is there a bit-twiddling algorithm to replace mid = (low + high) / 2 with something much faster?

Edit: Language is C#, but the equivalent bit-operation is valid in any language (although it may be of no performance benefit), which is why I left the C# tag off.

Answer 1

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

Be advised that using "(low + high) / 2" for midpoint calculations won't work correctly when integer overflow becomes an issue.

Answer 2

You can use bit shifting and also overcome a possible overflow issue:

low + ((high-low) >> 1)

However I must admit I expect modern compilers and interpreters to do division by 2 (or division by any other constant power of 2) as bit-shifting, so not sure if it will really help - try it out.

Answer 3

I'm skeptical that the finding of the midpoint is the bottleneck here. An integer division by two should be compiled to a right shift. Are high, low, and mid declared as integers?

I'd love to see your whole binary search routine. I think we're missing something here.

Answer 4

If I recall correctly, there are some cases where using the exact middle of the array can actually be slower. The solution is to randomize the choice of the index where you bisect the array. Equally true of the algorithm for determining the median of an array.

I can't recall the precise details, but I remember hearing in lecture 6 of the MIT algorithms series on iTunes.

Answer 5

Here is a bit-hack version of the average that does not suffer from the overflow problem:

unsigned int average (unsigned int x, unsigned int y)
{
  return (x&y)+((x^y)>>1);
}