The surprising part of this for me is the O(1) select lookup to find the upper bits, didn’t know that was possible, I think the relevant structure is in
https://arxiv.org/abs/0705.0552 . Took me a minute to then work through how that was used: There’s a string with concatenated unary counts of the upper bit patterns, and select_1(i) - i gives the number of zeroes before the ith bit, this number is the upper bit pattern the ith value uses.
Yeah I don’t remember today why I found that so surprising. There’s a lot of work to get the size down, but just a lookup table for select_1(i) is trivially O(1) once it’s constructed.
The surprising part of this for me is the O(1) select lookup to find the upper bits, didn’t know that was possible, I think the relevant structure is in https://arxiv.org/abs/0705.0552 . Took me a minute to then work through how that was used: There’s a string with concatenated unary counts of the upper bit patterns, and
select_1(i) - igives the number of zeroes before the ith bit, this number is the upper bit pattern the ith value uses.It comes down to clever use of popcount, doesnt it?
Yeah I don’t remember today why I found that so surprising. There’s a lot of work to get the size down, but just a lookup table for
select_1(i)is trivially O(1) once it’s constructed.