title: Efficiently compute the hashCode for a BitSet-like implementation of Set<Integer>
body: <p>I wonder, how to efficiently compute the <code>hashCode</code> for a <code>BitSet</code>-like implementation of <code>Set&lt;Integer&gt;</code>.</p>
  
  <p>The <code>BitSet#hashCode</code> is obviously fast to compute, rather stupid(*) and incompatible with <code>Set#hashCode()</code>.</p>
  
  <p>A fast compatible implementation could go like</p>
  
  <pre><code>int hashCode() {
      int result = 0;
      for (int i=0; i&lt;bits.length; ++i) {
          long word = bits[i];
          result += 64 * i * Long.bitCount(word) + weightedBitCount(word);
      }
      return result;
  }
  </code></pre>
  
  <p>if there was an efficient implementation of</p>
  
  <pre><code>int weightedBitCount(long word) { // naive implementation
      int result = 0;
      for (int i=0; i&lt;64; ++i) {
          if ((word &amp; (1L &lt;&lt; i)) != 0) {
              result += i;
          }
      }
      return result;
  }
  </code></pre>
  
  <p>In case most bits are unset, the naive implementation could be improved by testing <code>word==0</code> or using <code>Long.highestOneBit</code> or alike, but these tricks don't help much and are detrimental in other cases.</p>
  
  <p>Is there a clever trick to significantly speed it up in general?</p>
  
  <p><em>I guess, some batch computation over multiple words could be more efficient. Computing <code>Set#size</code> at the same time would be a nice bonus.</em></p>
  
  <p>A note concerning premature optimization: Yes, I know. I'm mostly curious (and it can be useful for things like Project Euler).</p>
  
  <hr>
  
  <p>(*) There are many bits which gets completely ignored (they get shifted out in the multiplication).</p>