Thread: Count Bits

Originally posted by krithi
(do not loop throught the bits).

well then how do you intend to do it? every method i can think of is, in one way or another, looping through the bits.

hmmm heres a loop through the bits method...

Code:

#include <stdio.h>

int main()
{
    int value=0x1234;// any number will do
    int count=0; // set bits
    int i;
    for(i=0;i<32;i++)
       if ((value<<i)&1) ++count;
    printf("Number of set bits is %d\n",count);
    return 0;
}

without looping through the bits im not so sure. Lookup tables will work but thats a hell of a lot more work.

>How to count number of 1's in a 32 bit integer (do not loop throught the bits).
Perhaps you're looking for this well known bit fiddling snippet?

Code:

unsigned countbits32_no_loop ( unsigned x )
{
   x = ( 0x55555555 & x ) + ( 0x55555555 & ( x >> 1 ) );
   x = ( 0x33333333 & x ) + ( 0x33333333 & ( x >> 2 ) );
   x = ( 0x0f0f0f0f & x ) + ( 0x0f0f0f0f & ( x >> 4 ) );
   x = ( 0x00ff00ff & x ) + ( 0x00ff00ff & ( x >> 8 ) );
   x = ( 0x0000ffff & x ) + ( 0x0000ffff & ( x >> 16 ) );

   return x;
}

-Prelude

oh that's just disgusting

I think id loop thru the bits.Why would you not want to? Salems look up table of 256 is workable but you would still need some calculations done adding the four bytes set bit counts together.
Preludes example tho clever is a maintainence programmers nightmare with hex numbers and shifts and no comments to help you see what the original programmer intended.It is not really self-documenting so should be commented.