How to count bits in a unsigned int?

Discussion in 'C Programming' started by tfeldman21@gmail.com, Feb 16, 2007.

  1. Guest

    On 32-bit platform,
    I am working on getting how many bits equal to 1 without an if loop.

    --
    Regards.
    Terrence Feldman
    Email:
    , Feb 16, 2007
    #1
    1. Advertising

  2. wrote:
    > On 32-bit platform,
    > I am working on getting how many bits equal to 1 without an if loop.


    Use a for loop or a while loop, testing each bit until you have no
    more bits to test. I'm not sure what an if loop would be like, unless
    you're using goto.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 16, 2007
    #2
    1. Advertising

  3. writes:
    > On 32-bit platform,
    > I am working on getting how many bits equal to 1 without an if loop.


    Your task is made easier by the fact that there's no such thing as an
    "if loop", so you won't have any trouble avoiding it.

    The most important step in solving any problem is defining exactly
    what the problem is. You haven't done that.

    But questions of the form "How can I do X without using feature Y?"
    are almost always homework assignments. We won't do your homework for
    you (unless you're willing to pay our exhorbitant consulting fees
    *and* let us submit our solutions directly to your instructor).

    We're quite willing to help you solve any problems in your C code, but
    we can't do that unless you write some and post it.

    --
    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, Feb 16, 2007
    #3
  4. CBFalconer Guest

    Harald van D?k wrote:
    > wrote:
    >
    >> On 32-bit platform, I am working on getting how many bits equal
    >> to 1 without an if loop.

    >
    > Use a for loop or a while loop, testing each bit until you have
    > no more bits to test. I'm not sure what an if loop would be like,
    > unless you're using goto.


    I have no idea what an 'if loop' is.

    unsigned int value, count;

    value = whatever;
    count = 0;

    /* loop invariant: count + bitsinvalue = bitsinwhatever */
    while (value) {
    count++;
    value = (value - 1) & value;
    }
    /* bitsinvalue = 0 */

    which doesn't care how wide an int is.

    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
    <http://www.securityfocus.com/columnists/423>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 16, 2007
    #4
  5. <> wrote in message n
    > On 32-bit platform,
    > I am working on getting how many bits equal to 1 without an if loop.
    >

    On the lowest bit can equal one. The rest equal 2, 4, 8 ... etc.

    So if (x & 1) is your answer.

    Tell your professor he means the number of set bits.
    Malcolm McLean, Feb 16, 2007
    #5
  6. CBFalconer wrote:
    > Harald van D?k wrote:
    > > wrote:
    > >
    > >> On 32-bit platform, I am working on getting how many bits equal
    > >> to 1 without an if loop.

    > >
    > > Use a for loop or a while loop, testing each bit until you have
    > > no more bits to test. I'm not sure what an if loop would be like,
    > > unless you're using goto.

    >
    > I have no idea what an 'if loop' is.
    > [example]
    > which doesn't care how wide an int is.


    And the way I mentioned does?

    count = value < 0;
    for (bit = 1; bit < INT_MAX / 2; bit *= 2)
    if (value & bit)
    count++;

    It accepts ints of any width.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 16, 2007
    #6
  7. Harald van Dijk wrote:
    > CBFalconer wrote:
    > > Harald van D?k wrote:
    > > > wrote:
    > > >
    > > >> On 32-bit platform, I am working on getting how many bits equal
    > > >> to 1 without an if loop.
    > > >
    > > > Use a for loop or a while loop, testing each bit until you have
    > > > no more bits to test. I'm not sure what an if loop would be like,
    > > > unless you're using goto.

    > >
    > > I have no idea what an 'if loop' is.
    > > [example]
    > > which doesn't care how wide an int is.

    >
    > And the way I mentioned does?
    >
    > count = value < 0;


    count = 0;

    > for (bit = 1; bit < INT_MAX / 2; bit *= 2)


    for (bit = 1; bit != 0; bit *= 2)

    > if (value & bit)
    > count++;
    >
    > It accepts ints of any width.


    The question asked for unsigned ints, but I posted an example for ints.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 16, 2007
    #7
  8. Harald van Dijk wrote:
    > Harald van Dijk wrote:
    > > CBFalconer wrote:
    > > > Harald van D?k wrote:
    > > > > wrote:
    > > > >
    > > > >> On 32-bit platform, I am working on getting how many bits equal
    > > > >> to 1 without an if loop.
    > > > >
    > > > > Use a for loop or a while loop, testing each bit until you have
    > > > > no more bits to test. I'm not sure what an if loop would be like,
    > > > > unless you're using goto.
    > > >
    > > > I have no idea what an 'if loop' is.
    > > > [example]
    > > > which doesn't care how wide an int is.

    > >
    > > And the way I mentioned does?
    > >
    > > count = value < 0;

    >
    > count = 0;
    >
    > > for (bit = 1; bit < INT_MAX / 2; bit *= 2)

    >
    > for (bit = 1; bit != 0; bit *= 2)
    >
    > > if (value & bit)
    > > count++;
    > >
    > > It accepts ints of any width.

    >
    > The question asked for unsigned ints, but I posted an example for ints.


    Sorry for replying to myself so much, but the example for ints was
    wrong anyway. After the loop exited, I needed to check value & bit
    once more, to see if the highest value bit was set.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 16, 2007
    #8
  9. Ksitami Guest

    static inline ulong bit_count(ulong x) {
    // Return number of bits set
    x = (0x55555555 & x) + (0x55555555 & (x>> 1)); // 0-2 in 2 bits
    x = (0x33333333 & x) + (0x33333333 & (x>> 2)); // 0-4 in 4 bits
    x = (0x0f0f0f0f & x) + (0x0f0f0f0f & (x>> 4)); // 0-8 in 8 bits
    x = (0x00ff00ff & x) + (0x00ff00ff & (x>> 8)); // 0-16 in 16
    bits
    x = (0x0000ffff & x) + (0x0000ffff & (x>>16)); // 0-31 in 32
    bits
    return x;
    }

    //Algorithms for programmers ideas and source code
    //by J¨org Arndt,
    Ksitami, Feb 16, 2007
    #9
  10. CoL Guest

    You also try recursion for the same....

    ~col

    On Feb 16, 3:03 pm, "Harald van Dijk" <> wrote:
    > CBFalconer wrote:
    > > Harald van D?k wrote:
    > > > wrote:

    >
    > > >> On 32-bit platform, I am working on getting how many bits equal
    > > >> to 1 without an if loop.

    >
    > > > Use a for loop or a while loop, testing each bit until you have
    > > > no more bits to test. I'm not sure what an if loop would be like,
    > > > unless you're using goto.

    >
    > > I have no idea what an 'if loop' is.
    > > [example]
    > > which doesn't care how wide an int is.

    >
    > And the way I mentioned does?
    >
    > count = value < 0;
    > for (bit = 1; bit < INT_MAX / 2; bit *= 2)
    >     if (value & bit)
    >         count++;
    >
    > It accepts ints of any width.
    CoL, Feb 16, 2007
    #10
  11. CoL wrote:

    > You also try recursion for the same....
    >
    > ~col


    To count bits? You're not in the business of performance eh?
    Christopher Layne, Feb 16, 2007
    #11
  12. CBFalconer Guest

    Harald van D?k wrote:
    >
    > CBFalconer wrote:
    > > Harald van D?k wrote:
    > > > wrote:
    > > >
    > > >> On 32-bit platform, I am working on getting how many bits equal
    > > >> to 1 without an if loop.
    > > >
    > > > Use a for loop or a while loop, testing each bit until you have
    > > > no more bits to test. I'm not sure what an if loop would be like,
    > > > unless you're using goto.

    > >
    > > I have no idea what an 'if loop' is.
    > > [example]
    > > which doesn't care how wide an int is.

    >
    > And the way I mentioned does?
    >
    > count = value < 0;
    > for (bit = 1; bit < INT_MAX / 2; bit *= 2)
    > if (value & bit)
    > count++;
    >
    > It accepts ints of any width.


    But it needs to know the precise type. My version will work when
    fed bytes, longs, shorts, etc. (with matching changes in the type
    of value, but making value an unsigned long will cover them all,
    except long long which may or may not be available).

    I find code fragments that need no editing more useful.
    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
    <http://www.securityfocus.com/columnists/423>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 16, 2007
    #12
  13. CBFalconer wrote:

    > But it needs to know the precise type. My version will work when
    > fed bytes, longs, shorts, etc. (with matching changes in the type
    > of value, but making value an unsigned long will cover them all,
    > except long long which may or may not be available).
    >
    > I find code fragments that need no editing more useful.


    What's wrong with the typical straightforward way?

    int bs(unsigned long v)
    {
    int c;

    for (c = 0; v; v >>= 1)
    c += v & 1;

    return c;
    }
    Christopher Layne, Feb 16, 2007
    #13
  14. CBFalconer wrote:
    > Harald van D?k wrote:
    > >
    > > CBFalconer wrote:
    > > > Harald van D?k wrote:
    > > > > wrote:
    > > > >
    > > > >> On 32-bit platform, I am working on getting how many bits equal
    > > > >> to 1 without an if loop.
    > > > >
    > > > > Use a for loop or a while loop, testing each bit until you have
    > > > > no more bits to test. I'm not sure what an if loop would be like,
    > > > > unless you're using goto.
    > > >
    > > > I have no idea what an 'if loop' is.
    > > > [example]
    > > > which doesn't care how wide an int is.

    > >
    > > And the way I mentioned does?
    > >
    > > count = value < 0;
    > > for (bit = 1; bit < INT_MAX / 2; bit *= 2)
    > > if (value & bit)
    > > count++;
    > >
    > > It accepts ints of any width.

    >
    > But it needs to know the precise type. My version will work when
    > fed bytes, longs, shorts, etc. (with matching changes in the type
    > of value, but making value an unsigned long will cover them all,
    > except long long which may or may not be available).
    >
    > I find code fragments that need no editing more useful.


    Your version will not work with signed types, and the version for
    unsigned types I posted later does not need editing either, as long as
    the type of 'bit' is large enough.
    =?utf-8?B?SGFyYWxkIHZhbiBExLNr?=, Feb 16, 2007
    #14
  15. CBFalconer Guest

    Christopher Layne wrote:
    > CBFalconer wrote:
    >
    >> But it needs to know the precise type. My version will work when
    >> fed bytes, longs, shorts, etc. (with matching changes in the type
    >> of value, but making value an unsigned long will cover them all,
    >> except long long which may or may not be available).
    >>
    >> I find code fragments that need no editing more useful.

    >
    > What's wrong with the typical straightforward way?
    >
    > int bs(unsigned long v)
    > {
    > int c;
    >
    > for (c = 0; v; v >>= 1)
    > c += v & 1;
    > return c;
    > }


    Nothing that I can see. It will take more cycles, for each 0 bit
    to the right of any 1 bit.

    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
    <http://www.securityfocus.com/columnists/423>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 16, 2007
    #15
  16. Radamanthe Guest

    Radamanthe, Feb 16, 2007
    #16
  17. pete Guest

    wrote:
    >
    > On 32-bit platform,
    > I am working on getting how many bits equal to 1 without an if loop.


    unsigned bit_count(unsigned n)
    {
    unsigned count;

    for (count = 0; n != 0; n &= n - 1) {
    ++count;
    }
    return count;
    }

    --
    pete
    pete, Feb 16, 2007
    #17
  18. jxh Guest

    On Feb 16, 5:01 am, Christopher Layne <> wrote:
    > CoL wrote:
    > > You also try recursion for the same....

    >
    > > ~col

    >
    > To count bits? You're not in the business of performance eh?


    Should perform just as well with proper optimizations:

    static int
    bits_r (unsigned int u, int count)
    {
    return !u ? count : bits_r(u & u-1, count+1);
    }

    int
    bits (unsigned int u)
    {
    return bits_r(u, 0);
    }

    -- James
    jxh, Feb 16, 2007
    #18
  19. dick Guest

    CBFalconer wrote:
    > Harald van D?k wrote:
    > > wrote:
    > >
    > >> On 32-bit platform, I am working on getting how many bits equal
    > >> to 1 without an if loop.

    > >
    > > Use a for loop or a while loop, testing each bit until you have
    > > no more bits to test. I'm not sure what an if loop would be like,
    > > unless you're using goto.

    >
    > I have no idea what an 'if loop' is.
    >
    > unsigned int value, count;
    >
    > value = whatever;
    > count = 0;
    >
    > /* loop invariant: count + bitsinvalue = bitsinwhatever */
    > while (value) {
    > count++;
    > value = (value - 1) & value;
    > }
    > /* bitsinvalue = 0 */
    >
    > which doesn't care how wide an int is.


    this is an interview question.

    i = 0;
    while(var)
    {
    var &= ~(-var);
    i++;
    }
    dick, Feb 17, 2007
    #19
  20. CBFalconer Guest

    dick wrote:
    > CBFalconer wrote:
    >> Harald van D?k wrote:
    >>> wrote:
    >>>
    >>>> On 32-bit platform, I am working on getting how many bits equal
    >>>> to 1 without an if loop.
    >>>
    >>> Use a for loop or a while loop, testing each bit until you have
    >>> no more bits to test. I'm not sure what an if loop would be like,
    >>> unless you're using goto.

    >>
    >> I have no idea what an 'if loop' is.
    >>
    >> unsigned int value, count;
    >>
    >> value = whatever;
    >> count = 0;
    >>
    >> /* loop invariant: count + bitsinvalue = bitsinwhatever */
    >> while (value) {
    >> count++;
    >> value = (value - 1) & value;
    >> }
    >> /* bitsinvalue = 0 */
    >>
    >> which doesn't care how wide an int is.

    >
    > this is an interview question.
    >
    > i = 0;
    > while(var)
    > {
    > var &= ~(-var);
    > i++;
    > }


    Doesn't work. Consider overflow (-var, for var == INT_MIN, 2'
    complement), sign-magnitude representation, 1's complement
    representation.

    --
    <http://www.cs.auckland.ac.nz/~pgut001/pubs/vista_cost.txt>
    <http://www.securityfocus.com/columnists/423>

    "A man who is right every time is not likely to do very much."
    -- Francis Crick, co-discover of DNA
    "There is nothing more amazing than stupidity in action."
    -- Thomas Matthews
    CBFalconer, Feb 17, 2007
    #20
    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:
    944
    Bob Hairgrove
    Oct 30, 2004
  2. Mockey Chen

    How to count bits in a unsigned int?

    Mockey Chen, Nov 13, 2005, in forum: C Programming
    Replies:
    11
    Views:
    536
    Emmanuel Delahaye
    Nov 14, 2005
  3. er
    Replies:
    6
    Views:
    488
    Andre Kostur
    Sep 14, 2007
  4. ciccio

    int*unsigned int = unsigned?

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

Share This Page