Re:Beautiful branchless binary search
by Dwedit on Friday April 28, 2023 @02:51AM
(#35738285)
For the case of comparing integers, and you want to know if A - B >= 0, you can take A - B, Arithmetic Shift Right 31 bits, then you have 0 if Greater Than or Equal and -1 if Less Than. From there you can just AND that with your displacement.
Note that it's not a comparison on A and B, it's a comparison on A - B, which must not overflow.
Note that it's not a comparison on A and B, it's a comparison on A - B, which must not overflow.