# Logic behind the program

Discussion in 'C Programming' started by ravi, Aug 29, 2007.

1. ### raviGuest

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

ravi, Aug 29, 2007

2. ### Walter RobersonGuest

In article <>,
ravi <> wrote:
>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.

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

Walter Roberson, Aug 29, 2007

3. ### Jack KleinGuest

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

> In article <>,
> ravi <> wrote:
> >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.

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

Jack Klein, Aug 30, 2007
4. ### Eric SosmanGuest

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

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
lid

Eric Sosman, Aug 30, 2007

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+(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.

--