Population count of rightmost n integers
- by Jason Baker
I'm implementing Bagwell's Ideal Hash Trie in Haskell. To find an element in a sub-trie, he says to do the following:
Finding the arc for a symbol s,
requires ?nding its corresponding bit
in the bit map and then counting the
one bits below it in the map to
compute an index into the ordered
sub-trie.
What is the best way to do this? It sounds like the most straightforward way of doing this is to select the bits below that bit and do a population count on the resulting number. Is there a faster or better way to do this?
