Re:Beautiful branchless binary search
by contravariant on Friday April 28, 2023 @05:41AM
(#35739267)
Don't you just need to remove the trailing 1s? In that case it's just `x & (x+1)`
[ Parent
| on HN ]
No, that would just set trailing 1s to 0. We want to trim them.
The idea behind trimming trailing 1s is that they represent a sub tree that is all smaller than the lower bound. By trimming those 1s, we traverse back up the tree to find the smallest number which is larger than or equal to the lower bound (aka the answer).