Velocity Reviews > Logic behind the program

Logic behind the program

ravi
Guest
Posts: n/a

 08-29-2007
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
Guest
Posts: n/a

 08-29-2007
In article <(E-Mail Removed) m>,
ravi <(E-Mail Removed)> 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

Jack Klein
Guest
Posts: n/a

 08-30-2007
On Wed, 29 Aug 2007 15:40:33 +0000 (UTC), http://www.velocityreviews.com/forums/(E-Mail Removed)-cnrc.gc.ca
(Walter Roberson) wrote in comp.lang.c:

> In article <(E-Mail Removed) m>,
> ravi <(E-Mail Removed)> 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

Eric Sosman
Guest
Posts: n/a

 08-30-2007
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
http://www.velocityreviews.com/forums/(E-Mail Removed)lid

Guest
Posts: n/a

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

--