[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Discuss-gnuradio] gr_count_bits32
From: |
Eric Blossom |
Subject: |
Re: [Discuss-gnuradio] gr_count_bits32 |
Date: |
Thu, 1 Dec 2005 14:43:55 -0800 |
User-agent: |
Mutt/1.5.6i |
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