Subj : Re: how does this work
To   : comp.programming
From : Alex Fraser
Date : Mon Aug 01 2005 03:22 am

<pacman2081@yahoo.com> wrote in message
news:1122852052.396558.147740@g43g2000cwa.googlegroups.com...
> 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);
>
> I have not been able to figure out how.

The nth line makes each adjacent group of 2^n bits in x equal the sum of the
the two (2^(n-1))-bit numbers which make up that group.

Alex

.