Logic behind the program

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

  1. ravi

    ravi Guest

    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
    #1
    1. Advertising

  2. 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
    #2
    1. Advertising

  3. ravi

    Jack Klein Guest

    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
    #3
  4. ravi

    Eric Sosman Guest

    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
    #4
  5. ravi

    Thad Smith Guest

    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.

    --
    Thad
     
    Thad Smith, Aug 30, 2007
    #5
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Francis Moreau

    The logic behind the C standard header files

    Francis Moreau, Nov 29, 2008, in forum: C Programming
    Replies:
    12
    Views:
    539
    James Kuyper
    Dec 1, 2008
  2. Borked Pseudo Mailed

    The logic behind the C standard header files

    Borked Pseudo Mailed, Nov 30, 2008, in forum: C Programming
    Replies:
    0
    Views:
    321
    Borked Pseudo Mailed
    Nov 30, 2008
  3. spike
    Replies:
    8
    Views:
    1,503
    Steve Holden
    Feb 9, 2010
  4. Michael W. Ryder
    Replies:
    10
    Views:
    179
    Mark Wilden
    May 21, 2008
  5. G G
    Replies:
    20
    Views:
    431
    Tim Rentsch
    Sep 23, 2013
Loading...

Share This Page