OdeToCode IC Logo

Bit Flipping the Binary Search Result

Sunday, October 9, 2005

When I did the Atlas hands on lab weeks ago, the following piece of code jumped out at me:

int index = Array.BinarySearch(



       new CaseInsensitiveComparer()



if (index < 0)


    index = ~index;


Why is the code doing a bitwise complement (~) on the return value of BinarySearch?

My next stop was the documentation for the return value of Array.BinarySearch, which states:

The index of the specified value in the specified array, if value is found. If value is not found and value is less than one or more elements in array, a negative number which is the bitwise complement of the index of the first element that is larger than value

In other words, if you don’t find an exact match you can flip all the bits and have an index pointing to something close – a good trick to know when building an auto-complete control.