title: Optimizing Long.bitCount
body: <p>I have a program that is making a huge number of calls to Long.bitCount(), so many that it is taking 33% of cycles on one CPU core.  Is there a way to implement it that is faster than the Sun JDK version?</p>
  
  <p>I have tried:</p>
  
  <ul>
  <li><a href="http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel" rel="nofollow noreferrer">This algorithm</a> (I think this is exactly how the JDK implements it)</li>
  <li>lookup tables of various sizes between 2<sup>8</sup> and 2<sup>22</sup> (looking at a few bits at a time and adding the results)</li>
  </ul>
  
  <p>But I couldn't do any better than a 2<sup>16</sup>-entry lookup table with a manually-unrolled loop (about 27% CPU.)<br>
  How else might this be optimized for Java?</p>
  
  <hr>
  
  <p><strong>Note</strong>: this question is about Java-specific optimization, but <a href="https://stackoverflow.com/q/109023/12048">this similar (language-agnostic) question</a> has many other algorithms.</p>