> From
> my.opera.com/allbits/blog/show.dml/114980
> which has a whole slew of interesting operations.
>
> It's a start.
>
> ----------
> 13. Population Count (Ones Count)
>
> The population count of a binary integer value x is
> the number of one
> bits in the value. Although many machines have
> single instructions for
> this, the single instructions are usually microcoded
> loops that test a
> bit per cycle; a log-time algorithm coded in C is
> often faster. The
> following code uses a variable-precision SWAR
> algorithm to perform a
> tree reduction adding the bits in a 32-bit value:
>
> unsigned int
> ones32(register unsigned int x)
> {
> /* 32-bit recursive reduction using SWAR...
> but first step is mapping 2-bit values
> into sum of 2 1-bit values in sneaky way
> */
> x -= ((x >> 1) & 0x55555555);
> x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
> x = (((x >> 4) + x) & 0x0f0f0f0f);
> x += (x >> 8);
> x += (x >> 16);
> return(x & 0x0000003f);
> }
>
> ----------
>
> On 1/29/07, Carlos A. Marcano V.
> <c.marcanoKILLspamgmail.com> wrote:
> > This one is making me go crazy. I know there is a
> well-known solution
> > for detecting the number of 'ones' in a byte using
> logic gates (just as
> > you might use XOR's for parity check) but I just
> can't simply remember!
> >
> > Do any of you guys do remember it?
> >
> > Regards,
> >
> > *Carlos Marcano*
> > -Guri, Venezuela-
> > --

> From
> my.opera.com/allbits/blog/show.dml/114980
> which has a whole slew of interesting operations.
>
> It's a start.
>
> ----------
> 13. Population Count (Ones Count)
>
> The population count of a binary integer value x is the number of one
> bits in the value. Although many machines have single instructions for
> this, the single instructions are usually microcoded loops that test a
> bit per cycle; a log-time algorithm coded in C is often faster. The
> following code uses a variable-precision SWAR algorithm to perform a
> tree reduction adding the bits in a 32-bit value:
>
> unsigned int
> ones32(register unsigned int x)
> {
> /* 32-bit recursive reduction using SWAR...
> but first step is mapping 2-bit values
> into sum of 2 1-bit values in sneaky way
> */
> x -= ((x >> 1) & 0x55555555);
> x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
> x = (((x >> 4) + x) & 0x0f0f0f0f);
> x += (x >> 8);
> x += (x >> 16);
> return(x & 0x0000003f);
> }
>
> ----------
>

> This one is making me go crazy. I know there is a well-known solution
> for detecting the number of 'ones' in a byte using logic gates (just as
>  you might use XOR's for parity check) but I just can't simply
> remember!
>
> Do any of you guys do remember it?
>
> Regards,
>
> *Carlos Marcano*
> -Guri, Venezuela-

> From
> my.opera.com/allbits/blog/show.dml/114980
> which has a whole slew of interesting operations.
>
> It's a start.
>
> ----------
> 13. Population Count (Ones Count)
>
> The population count of a binary integer value x is the number of one
> bits in the value. Although many machines have single instructions for
> this, the single instructions are usually microcoded loops that test a
> bit per cycle; a log-time algorithm coded in C is often faster. The
> following code uses a variable-precision SWAR algorithm to perform a
> tree reduction adding the bits in a 32-bit value:
>
> unsigned int
> ones32(register unsigned int x)
> {
> /* 32-bit recursive reduction using SWAR...
> but first step is mapping 2-bit values
> into sum of 2 1-bit values in sneaky way
> */
> x -= ((x >> 1) & 0x55555555);
> x = (((x >> 2) & 0x33333333) + (x & 0x33333333));
> x = (((x >> 4) + x) & 0x0f0f0f0f);
> x += (x >> 8);
> x += (x >> 16);
> return(x & 0x0000003f);
> }
>
> ----------
>