title: Count the number of bits set using only bitwise operations
body: <blockquote>
    <p><strong>Possible Duplicate:</strong><br>
    <a href="https://stackoverflow.com/questions/109023/best-algorithm-to-count-the-number-of-set-bits-in-a-32-bit-integer">Best algorithm to count the number of set bits in a 32-bit integer?</a>  </p>
  </blockquote>
  
  
  
  <p>Using only ! ~ &amp; ^ | + &lt;&lt; >> operators, I need to count the number of bits set in a 32 bit integer while only accessing directly 8 bits. So only 0xaa not 0xaaaa</p>
  
  <p>Ex. 0x07 = 3 and 0x05 = 2</p>
  
  <p>I also can only use a max of 40 operators. </p>
  
  <p>Right now my solution uses 90 and is:</p>
  
  <pre><code>int countBitsSet(int x)
  {
  int count = 0;
  int mask = 0x01 // 00000001
  
  count = (x &amp; mask);
  count += (x &gt;&gt; 1) &amp; mask;
  count += (x &gt;&gt; 2) &amp; mask;
  .
  .
  .
  count += (x &gt;&gt; 31) &amp; mask;
  
  return count;
  }
  </code></pre>
  
  <p>Does anyone know of a way to reduce this step by half? I was thinking of finding a way to do it in parallel or something and count 4 bits at once but I cant figure out how. Other people have done it in 25 operators so I know there is a way. Any ideas?</p>