Some bitwise problems..

[Twey]

I don't believe there is an O(1) solution, but there is an O(number of ones) algorithm involving repeatedly eliminating the least significant bit:

short int oneBits(short int n) {
  short int total;

  if (!n) return 0;

  for (total = 1; n ^= ((n - 1) ^ n) & n; ++total);

  return total;  
}

To break it down, it works like this:

• let n = 010111010b
• n - 1 = 010111001 // subtract 1 to change all the bits up to the bit we're interested in
• (n - 1) ^ n = 000000011 // XOR it with the original value to get only the changed bits (those up to and including the interesting bit)
• ((n - 1) ^ n) & n = 0000000010 // AND that with the original value to set only the interesting bit
• n ^ (((n - 1) ^ n) & n) = 010111000 // XOR that with the original value to flip the interesting bit
• if the new value of n is 0, we have no more 1 bits left, so exit

Edit: ah! There's a simpler algorithm to do the same thing in the top link in the post above (by ahoodin). Silly that I didn't see that *learns*