Logic behind the program

[ravi]

Hello,
the code below calculate the number of bits set in an unsigned
integer.
Can you explain me the logic behind the code?

unsigned int x = Some number;

x=(0xaaaaaaaa&x )>>1+(0x5555555 5&x);
x=(0xcccccccc&x )>>2+(0x3333333 3&x);
x=(0xf0f0f0f0&x )>>4+(0x0f0f0f0 f&x);
x=(0xff00ff00&x )>>8+(0x00ff00f f&x);
x=x>>16+(0x0000 ffff&x));

[Walter Roberson]

In article <11************ ********@e9g200 0prf.googlegrou ps.com>,
ravi <dc**********@g mail.comwrote:

>the code below calculate the number of bits set in an unsigned
integer.
Can you explain me the logic behind the code?

>unsigned int x = Some number;

>x=(0xaaaaaaaa& x)>>1+(0x555555 55&x);
x=(0xcccccccc& x)>>2+(0x333333 33&x);
x=(0xf0f0f0f0& x)>>4+(0x0f0f0f 0f&x);
x=(0xff00ff00& x)>>8+(0x00ff00 ff&x);
x=x>>16+(0x000 0ffff&x));

That code has floated around a long time, and you could
probably find an explanation for it in the archives.

But you are incorrect that it calculates the number of
bits set in an unsigned integer. It only calculates
the number of bits set in 32 bit unsigned integers.
If your unsigned integers are wider than that, it will
not work.

--
Prototypes are supertypes of their clones. -- maplesoft

[Jack Klein]

On Wed, 29 Aug 2007 15:40:33 +0000 (UTC), ro******@ibd.nr c-cnrc.gc.ca
(Walter Roberson) wrote in comp.lang.c:

In article <11************ ********@e9g200 0prf.googlegrou ps.com>,
ravi <dc**********@g mail.comwrote:

the code below calculate the number of bits set in an unsigned
integer.
Can you explain me the logic behind the code?

unsigned int x = Some number;

x=(0xaaaaaaaa&x )>>1+(0x5555555 5&x);
x=(0xcccccccc&x )>>2+(0x3333333 3&x);
x=(0xf0f0f0f0&x )>>4+(0x0f0f0f0 f&x);
x=(0xff00ff00&x )>>8+(0x00ff00f f&x);
x=x>>16+(0x0000 ffff&x));

That code has floated around a long time, and you could
probably find an explanation for it in the archives.

But you are incorrect that it calculates the number of
bits set in an unsigned integer. It only calculates
the number of bits set in 32 bit unsigned integers.
If your unsigned integers are wider than that, it will
not work.

Platforms with unsigned ints wider than 32 bits are rare but do exist.

On the other hand, platforms with unsigned int narrower than 32 bits
are still very common, although not on the desktop.

On a platform with 24-bit (un)signed ints, and there have been some,
it will produce the correct result.

On a platform with 16-bit (un)signed ints, the code invokes undefined
behavior.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://c-faq.com/
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html

[Eric Sosman]

ravi wrote:

Hello,
the code below calculate the number of bits set in an unsigned
integer.
Can you explain me the logic behind the code?

unsigned int x = Some number;

x=(0xaaaaaaaa&x )>>1+(0x5555555 5&x);
x=(0xcccccccc&x )>>2+(0x3333333 3&x);
x=(0xf0f0f0f0&x )>>4+(0x0f0f0f0 f&x);
x=(0xff00ff00&x )>>8+(0x00ff00f f&x);
x=x>>16+(0x0000 ffff&x));

The easiest way to understand it may be to draw
a picture. (Warning: Bad ASCII art for the 8-bit case
follows).

x = abcdefgh[2]
/ \
/ \
a b c d e f g h a b c d e f g h
& 1 0 1 0 1 0 1 0 & 0 1 0 1 0 1 0 1
= a 0 c 0 e 0 g 0 = 0 b 0 d 0 f 0 h

>>1 = 0 a 0 c 0 e 0 g : : : :

\ : : : :
- + 0 a 0 c 0 e 0 g
= ? ? ? ? ? ? ? ? = y

This is the first step. Can you explain the rightmost
two bits of the final sum in terms of the number of 1's
in the rightmost two bits of the original x? How about
the other three pairs? With that explanation in mind,
can you diagram what happens to y in the next step, and
the significance of its two quartets of bits?

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Thad Smith]

ravi wrote:
ravi wrote:

Hello,
the code below calculate the number of bits set in an unsigned
integer.
Can you explain me the logic behind the code?

unsigned int x = Some number;

x=(0xaaaaaaaa&x )>>1+(0x5555555 5&x);
x=(0xcccccccc&x )>>2+(0x3333333 3&x);
x=(0xf0f0f0f0&x )>>4+(0x0f0f0f0 f&x);
x=(0xff00ff00&x )>>8+(0x00ff00f f&x);
x=x>>16+(0x0000 ffff&x));

You need to add parentheses around the shift expression for the
calculation to work correctly.

--
Thad