Subj : Re: how does this work
To   : comp.programming
From : Jason Curl
Date : Wed Aug 03 2005 07:14 pm

pacman2081@yahoo.com wrote:
> This piece of code counts the number of one bits in integer x.
> 
> unsigned int x;
> 
> x = (x & 0x55555555) + ((x>>1)&0x55555555);
> x = (x & 0x33333333) + ((x>>2)&0x33333333);
> x = (x & 0x0F0F0F0F) + ((x>>4)&0x0F0F0F0F);
> x = (x & 0x00FF00FF) + ((x>>8)&0x00FF00FF);
> x = (x & 0x0000FFFF) + ((x>>16)&0x0000FFFF);

There's a pattern there. The first line is testing groups of 1 bit, the 
second groups of 2 bits, the third groups of 4 bits, the fourth groups 
of 8 bits and the last groups of 16 bits.

If we take just the first line, it can be seen how the rest of it works:

Let's say 'x' is abcdefghijklmnop

Line 1  0b0d0f0h0j0l0n0p
        +0a0c0e0g0i0k0m0o
         ----------------
       x=AABBCCDDEEFFGGHH

i.e. look at the lower two bits.
   p=0, o=0 => HH=0, ie 0 bits
   p=1, o=0 => HH=1, ie 1 bit
   p=0, o=1 => HH=1, ie 1 bit
   p=1, o=1 => HH=2, ie 2 bits

Similarly for GG, FF, EE, DD, CC, BB and AA. Now, you should be able to 
see why in the second line there is a shift right of 2, and a mask of 
two bits grouped together.

Line 2 00BB00DD00FF00HH
       +00AA00CC00EE00GG
        ----------------
        qqqqrrrrsssstttt

i.e. now 'tttt' contains the number of bits set in 'mnop'

> 
> 
> I have not been able to figure out how.
> -- pacman
>

.