number of 1's in 32 bit number

Question

I am lookin for a method to have number of 1's in 32 bit number without using a loop in between. can any body help me and provide me the code or algorithm to do so. Thanks in advance.

Answer 1

See the canonical reference: Bit Twiddling Hacks

Answer 2

Split the 32 bit number into four 8 bit numbers (see bit shifting operator, casting etc.)

Then use a lookup with 256 entries that converts the 8 bit number into a count of bits set. Add the four results, presto!

Also, see what Mitch Wheat said - bit fiddling can be a lot of fun ;)

Answer 3

See Integer.bitCount(int). You can refer to the source code if you want to see how it works; many of the Integer class's bit twiddling routines are taken from Hacker's Delight.

Answer 4

You can define it recursively:

int bitcount(int x) {
  return (x==0) ? 0 : (x & 1 + bitcount(x/2));
}

The code above is not tested, and probably only works for x>=0. Hopefully, you will get the idea anyways...

Answer 5

My personal favourite, directly from Bit Twiddling Hacks:

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

Answer 6

Short, obscenely optimized answer (in C):

int pop(unsigned x) {
   x = x - ((x >> 1) & 0x55555555);
   x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
   x = (x + (x >> 4)) & 0x0F0F0F0F;
   x = x + (x >> 8);
   x = x + (x >> 16);
   return x & 0x0000003F;
}

To see why this magic works, see The Quest for an Accelerated Population Count by Henry S. Warren, Jr. chapter 10 in Beautiful Code.