# Bit Counting

Discussion in 'C Programming' started by GJ, Oct 20, 2005.

1. ### GJGuest

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

GJ, Oct 20, 2005

2. ### Alex FraserGuest

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

Alex Fraser, Oct 20, 2005

3. ### Julian V. NobleGuest

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

^^^^^^^^^^^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

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

Julian V. Noble, Oct 20, 2005
4. ### Peter NilssonGuest

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 Nilsson, Oct 21, 2005