title: Population count of rightmost n integers
body: <p>I'm implementing <a href="http://lampwww.epfl.ch/papers/idealhashtrees.pdf" rel="nofollow noreferrer">Bagwell's Ideal Hash  Trie</a> in Haskell.  To find an element in a sub-trie, he says to do the following:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>What is the best way to do this?  It sounds like the most straightforward way of doing this is to <a href="https://stackoverflow.com/questions/2798191/extracting-rightmost-n-bits-of-an-integer">select the bits below that bit</a> and do a population count on the resulting number.  Is there a faster or better way to do this?</p>