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+(0x55555555&x);
x=(0xcccccccc&x)>>2+(0x33333333&x);
x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x);
x=(0xff00ff00&x)>>8+(0x00ff00ff&x);
x=x>>16+(0x0000ffff&x));

 

[Walter Roberson]

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+(0x55555555&x);
x=(0xcccccccc&x)>>2+(0x33333333&x);
x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x);
x=(0xff00ff00&x)>>8+(0x00ff00ff&x);
x=x>>16+(0x0000ffff&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.

 

[Jack Klein]

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.learn.c-c++
http://www.club.cc.cmu.edu/~ajo/docs/FAQ-acllc.html

 

[Eric Sosman]

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+(0x55555555&x);
x=(0xcccccccc&x)>>2+(0x33333333&x);
x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x);
x=(0xff00ff00&x)>>8+(0x00ff00ff&x);
x=x>>16+(0x0000ffff&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 \ : : : :
-> + 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?

 

[Thad Smith]

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+(0x55555555&x);
x=(0xcccccccc&x)>>2+(0x33333333&x);
x=(0xf0f0f0f0&x)>>4+(0x0f0f0f0f&x);
x=(0xff00ff00&x)>>8+(0x00ff00ff&x);
x=x>>16+(0x0000ffff&x));

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