Pretty cool stuff. The algorithm returns the largest item that’s at most the size of x. At each step it checks array[k] and then checks either 2k or 2k+1 next.
The last k will be past the end of the array so you have to backtrack to discover the actual lower bound.
k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s.
How to do that though? There’s an assembly instruction called ffs that will give you the first bit set from the right side. So invert k to get 010000, ffs gives you 4. So for k 101111, shift forward by 4, you get 10. Cancel the right turns, now you have the index of the lower bound.
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).
The last k will be past the end of the array so you have to backtrack to discover the actual lower bound.
k records it’s turns in binary such as 10111. After another right turn it’s 101111. So to backtrack, you strip off the trailing 1s.
How to do that though? There’s an assembly instruction called ffs that will give you the first bit set from the right side. So invert k to get 010000, ffs gives you 4. So for k 101111, shift forward by 4, you get 10. Cancel the right turns, now you have the index of the lower bound.