Re: [Discuss-gnuradio] gr_count_bits32

[Eric Blossom]

On Thu, Dec 01, 2005 at 08:50:49AM +0100, Stephane Fillod wrote:
> > > Nor can I make out how this code counts bits?
> > > 
> > > // return number of set bits in the low 32 bits of x
> > > int 
> > > gr_count_bits32 (int x)
> > > {
> > >   int     count = 0;
> > > 
> > >   for (int i = 0; i < 32; i++)
> > >     if (x & (1 << i))
> > >       count++;
> > > 
> > >   return count;
> > > }
> 
> This is also known as the hamming weight (i.e. the number
> of bits set) of a 32-bit word. Here is a faster algorithm:
> 
> unsigned int
> gr_count_bits32 (unsigned int x)
> {
>   unsigned res = (x & 0x55555555) + ((x >> 1) & 0x55555555);
>   res = (res & 0x33333333) + ((res >> 2) & 0x33333333);
>   res = (res & 0x0F0F0F0F) + ((res >> 4) & 0x0F0F0F0F);
>   res = (res & 0x00FF00FF) + ((res >> 8) & 0x00FF00FF);
>   return (res & 0x0000FFFF) + ((res >> 16) & 0x0000FFFF);
> }
> 

Thanks!  Much faster, and even easier to understand (not!).
I've committed it to CVS.

This is also sometimes called "pop count" or "population count".
Certain machines favored by the NSA have had a single instruction for
this operation ;)

Eric