Bit Counting

[GJ]

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

 

[Alex Fraser]

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. [code reformatted]
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));

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

 

[Julian V. Noble]

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

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
(e-mail address removed)
^^^^^^^^^^^^^^^^^^
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.

 

[Peter Nilsson]

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));

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.)