Bit Counting

I came accross the following code snippet to count the number of 1 bit in a word (32bit in this case). However I am not able to understand it thoroughly.. Could anyone please explain this.

===============================================

x = (0x55555555 & x) + (0x55555555 & (x>> 1)); x = (0x33333333 & x) + (0x33333333 & (x>> 2)); x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8)); x = (0x0000ffff & x) + (0x0000ffff & (x>>16));========================================= ======

Regards,

GJ

re: Bit Counting

"GJ" <gauravbjain@gmail.com> wrote in message
news:dj839b$2q5@netnews.net.lucent.com...[color=blue]
> I came accross the following code snippet to count the number of 1 bit in
> a word (32bit in this case). However I am not able to understand it
> thoroughly.. Could anyone please explain this.[/color]
[code reformatted][color=blue]
> x = (0x55555555 & x) + (0x55555555 & (x>> 1));
> x = (0x33333333 & x) + (0x33333333 & (x>> 2));
> x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4));
> x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8));
> x = (0x0000ffff & x) + (0x0000ffff & (x>>16));[/color]

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

Alex

re: Bit Counting

> GJ wrote:[color=blue]
>
> I came accross the following code snippet to count the number of 1 bit in a
> word (32bit in this case). However I am not able to understand it thoroughly..
> Could anyone please explain this.
>
> ===============================================
>
> x = (0x55555555 & x) + (0x55555555 & (x>> 1));
>
> x = (0x33333333 & x) + (0x33333333 & (x>> 2));
>
> x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4));
>
> x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8));
>
> x = (0x0000ffff & x) + (0x0000ffff & (x>>16));
>
> ===============================================
>
> Regards,
>
> GJ[/color]

You will find this in "Hacker's Delight" by Warren on p. 65.
Basically it is divide-and-conquer. Warren explains it in detail.


--
Julian V. Noble
Professor Emeritus of Physics
jvn@lessspamformother.virginia.edu
^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"For there was never yet philosopher that could endure the
toothache patiently."

-- Wm. Shakespeare, Much Ado about Nothing. Act v. Sc. 1.

re: Bit Counting

GJ wrote:[color=blue]
> I came accross the following code snippet to count the number of 1 bit
> in a word (32bit in this case). However I am not able to understand it
> thoroughly.. Could anyone please explain this.
>
> x = (0x55555555 & x) + (0x55555555 & (x>> 1));
> x = (0x33333333 & x) + (0x33333333 & (x>> 2));
> x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4));
> x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8));
> x = (0x0000ffff & x) + (0x0000ffff & (x>>16));[/color]

Consider the decimal case of showing the sum of digits in the number
12738349 (37)...

12738349
\/\/\/\/
03101113 (1+2, 7+3, 8+3, 4+9)
\ / \ /
00130024 (3+10, 11+13)
\ /
00000037 (13+24)

The code above does the same thing, only bitwise for binary (and with
extra iterations for the extra initial digits.)

--
Peter