Subj : Re: how does this work
To   : comp.programming
From : Willem
Date : Mon Aug 01 2005 10:51 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);

This line takes each even bit and adds it to the odd bit that follows it.
That means that each pair of bits now contains the sum of two bits.

) x = (x & 0x33333333) + ((x>>2)&0x33333333);

This adds each even pair of bits to the pair of bits that follows it.
This means that each group of four bits contains the sum of those pairs
of bits, and therefore the sum of the four bits that were there.

) x = (x & 0x0F0F0F0F) + ((x>>4)&0x0F0F0F0F);

And so on.

) x = (x & 0x00FF00FF) + ((x>>8)&0x00FF00FF);
) x = (x & 0x0000FFFF) + ((x>>16)&0x0000FFFF);
)
)
) I have not been able to figure out how.

It's quite similar to SIMD instructions
(single instruction, multiple data).

That is, one 32-bit addition actually does 16 2-bit additions.
Or 8 4-bit additions.  Or 4 8-bit additions.
The masking and shifting makes sure the right things are added.


SaSW, Willem
-- 
Disclaimer: I am in no way responsible for any of the statements
            made in the above text. For all I know I might be
            drugged or something..
            No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

.