Hey bit twiddling twitter: I am trying to map an append only binary tree to an append only array. The offset of a leaf node is offset = 2 * index - count_one_bits(index) Any ideas how to write the inverse function? Index from offset?
Replying to @klaehnr
Unfortunately, not append only, but I wonder if it can be extended to support it? https://github.com/stripe/bonsai/blob/master/bonsai-core/src/main/scala/com/stripe/bonsai/IndexedBitSet.scala … An implementation of: http://www.dcc.uchile.cl/~gnavarro/algoritmos/ps/wea05.pdf … (rank gives you count of 1s, select is inverse)
6:27 AM - 22 May 2020
0 replies
0 retweets
2 likes
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.