How to count bits in a unsigned int?

Discussion in 'C Programming' started by Mockey Chen, Nov 13, 2005.

  1. Mockey Chen

    Mockey Chen Guest

    On 32-bit platform, give you a unsigned int?
    what is the best way to get how many bits equal to 1.
    please do not use loop if possible?

    Thanks in advance.

    --
    Regards.
    Mockey Chen
    Email:
     
    Mockey Chen, Nov 13, 2005
    #1
    1. Advertising

  2. Mockey Chen

    Guest

    Mockey Chen wrote:
    > On 32-bit platform, give you a unsigned int?
    > what is the best way to get how many bits equal to 1.
    > please do not use loop if possible?


    Use the GMP library:

    [Function] unsigned long int mpz popcount (mpz_t op)
    If op  0, return the population count of op, which is the number of 1
    bits in the binary
    representation. If op < 0, the number of 1s is infinite, and the return
    value is MAX ULONG,
    the largest possible unsigned long.


    >
    > Thanks in advance.
    >
    > --
    > Regards.
    > Mockey Chen
    > Email:
     
    , Nov 13, 2005
    #2
    1. Advertising

  3. "Mockey Chen" <> writes:
    > On 32-bit platform, give you a unsigned int?
    > what is the best way to get how many bits equal to 1.
    > please do not use loop if possible?


    The "please do not use loop if possible" clause makes this sound very
    much like homework. If so, please give us your instructor's e-mail
    address so we can submit the answer directly.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
    We must do something. This is something. Therefore, we must do this.
     
    Keith Thompson, Nov 13, 2005
    #3
  4. Mockey Chen

    Guest

    Mockey Chen wrote:
    > On 32-bit platform, give you a unsigned int?
    > what is the best way to get how many bits equal to 1.
    > please do not use loop if possible?


    Look for "Pop Count" in AMD's Optimization documentation. They give a
    very fast algorithm.

    --
    Paul Hsieh
    http://www.pobox.com/~qed/
    http://bstring.sf.net/
     
    , Nov 13, 2005
    #4
  5. Mockey Chen

    Mockey Chen Guest

    oops, homework? I never asked anyone to help me because of homework
    when I was a student.

    I saw this question in another bulletin board system. they guies give some
    solutions for this topic, but not perfect, so I copy the question to here.

    Since there are guru in this news group, I thought I can get a more better.
    Now, I got a perfect answer is homework, haha. I become a student again.


    "Keith Thompson" <> wrote:...
    > "Mockey Chen" <> writes:
    >> On 32-bit platform, give you a unsigned int?
    >> what is the best way to get how many bits equal to 1.
    >> please do not use loop if possible?

    >
    > The "please do not use loop if possible" clause makes this sound very
    > much like homework. If so, please give us your instructor's e-mail
    > address so we can submit the answer directly.
    >
    > --
    > Keith Thompson (The_Other_Keith)
    > <http://www.ghoti.net/~kst>
    > San Diego Supercomputer Center <*>
    > <http://users.sdsc.edu/~kst>
    > We must do something. This is something. Therefore, we must do this.
     
    Mockey Chen, Nov 13, 2005
    #5
  6. Mockey Chen

    pete Guest

    pete, Nov 13, 2005
    #6
  7. In article <>,
    Keith Thompson <> wrote:

    > "Mockey Chen" <> writes:
    > > On 32-bit platform, give you a unsigned int?
    > > what is the best way to get how many bits equal to 1.
    > > please do not use loop if possible?

    >
    > The "please do not use loop if possible" clause makes this sound very
    > much like homework. If so, please give us your instructor's e-mail
    > address so we can submit the answer directly.


    But it is very simple (assuming thirtytwo bit unsigned int):

    int bitcount (unsigned int x)
    {
    return
    ((x & (1u << 0)) != 0) +
    ((x & (1u << 1)) != 0) +
    ((x & (1u << 2)) != 0) +
    ((x & (1u << 3)) != 0) +
    ((x & (1u << 4)) != 0) +
    ((x & (1u << 5)) != 0) +
    ((x & (1u << 6)) != 0) +
    ((x & (1u << 7)) != 0) +
    ((x & (1u << 8)) != 0) +
    ((x & (1u << 9)) != 0) +
    ((x & (1u << 10)) != 0) +
    ((x & (1u << 11)) != 0) +
    ((x & (1u << 12)) != 0) +
    ((x & (1u << 13)) != 0) +
    ((x & (1u << 14)) != 0) +
    ((x & (1u << 15)) != 0) +
    ((x & (1u << 16)) != 0) +
    ((x & (1u << 17)) != 0) +
    ((x & (1u << 18)) != 0) +
    ((x & (1u << 19)) != 0) +
    ((x & (1u << 20)) != 0) +
    ((x & (1u << 21)) != 0) +
    ((x & (1u << 22)) != 0) +
    ((x & (1u << 23)) != 0) +
    ((x & (1u << 24)) != 0) +
    ((x & (1u << 25)) != 0) +
    ((x & (1u << 26)) != 0) +
    ((x & (1u << 27)) != 0) +
    ((x & (1u << 28)) != 0) +
    ((x & (1u << 29)) != 0) +
    ((x & (1u << 30)) != 0) +
    ((x & (1u << 31)) != 0);
    }

    No loop!
     
    Christian Bau, Nov 13, 2005
    #7
  8. Mockey Chen

    Jordan Abel Guest

    On 2005-11-13, Mockey Chen <> wrote:
    > On 32-bit platform, give you a unsigned int?
    > what is the best way to get how many bits equal to 1.
    > please do not use loop if possible?
    >
    > Thanks in advance.


    Make a lookup table with 256 elements. check each 8-bit group in
    turn. unsigned char weight[256] = {
    0, 1, 1, 2, 1, 2, 2, 3,
    }; etc
     
    Jordan Abel, Nov 13, 2005
    #8
  9. Mockey Chen

    Mockey Chen Guest

    Excellent. thanks.

    I find a solution in c++:

    #include <bitset>
    #include <iostream>
    int main()
    {
    unsigned long x;
    std::cin >> x;
    std::bitset<32> bs(x);
    std::cout << bs.count() << std::endl;
    return 0;
    }


    "pete" <> wrote:...
    > Mockey Chen wrote:
    >>
    >> On 32-bit platform, give you a unsigned int?
    >> what is the best way to get how many bits equal to 1.
    >> please do not use loop if possible?

    >
    > First day on the net?
    >
    > http://www.google.com/search?hl=en&ie=ISO-8859-1&q=counts bits C 32
    >
    > http://www-db.stanford.edu/~manku/bitcount/bitcount.html
    >
    > --
    > pete
     
    Mockey Chen, Nov 14, 2005
    #9
  10. On Sun, 13 Nov 2005 12:09:07 +0800, "Mockey Chen"
    <> wrote:

    >On 32-bit platform, give you a unsigned int?
    >what is the best way to get how many bits equal to 1.
    >please do not use loop if possible?
    >
    >Thanks in advance.


    The "best way" in my book uses a loop:

    unsigned int bit_count(unsigned int n)
    {
    unsigned int count = 0;
    while (n)
    {
    /* clear rightmost '1' bit */
    n &= (n-1);
    count++;
    }
    return count;
    }

    Ref: "Hacker's Delight"

    Roberto Waltman

    [ Please reply to the group, ]
    [ return address is invalid. ]
     
    Roberto Waltman, Nov 14, 2005
    #10
  11. Mockey Chen

    Flash Gordon Guest

    Mockey Chen wrote:
    > Excellent. thanks.
    >
    > I find a solution in c++:


    <snip>

    1) Please don't top post. You reply belongs under the text you are
    replying to (after suitable trimming), not above. See most of the
    posts on this group for examples.

    2) We don't care about C++ solutions here, this is comp.lang.c. If you
    want C++ go to comp.lang.c++

    > "pete" <> wrote:...


    <snip>
    --
    Flash Gordon
    Living in interesting times.
    Although my email address says spam, it is real and I read it.
     
    Flash Gordon, Nov 14, 2005
    #11
  12. Mockey Chen a écrit :
    > On 32-bit platform, give you a unsigned int?
    > what is the best way to get how many bits equal to 1.
    > please do not use loop if possible?


    Use recursion.

    --
    A+

    Emmanuel Delahaye
     
    Emmanuel Delahaye, Nov 14, 2005
    #12
    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. Timo Freiberger
    Replies:
    3
    Views:
    952
    Bob Hairgrove
    Oct 30, 2004
  2. Replies:
    19
    Views:
    1,517
    CBFalconer
    Feb 17, 2007
  3. er
    Replies:
    6
    Views:
    491
    Andre Kostur
    Sep 14, 2007
  4. ciccio

    int*unsigned int = unsigned?

    ciccio, Jun 4, 2010, in forum: C++
    Replies:
    2
    Views:
    413
    Öö Tiib
    Jun 4, 2010
  5. pozz
    Replies:
    12
    Views:
    744
    Tim Rentsch
    Mar 20, 2011
Loading...

Share This Page