Bit count of an integer

Discussion in 'C Programming' started by lovecreatesbea...@gmail.com, Nov 5, 2007.

  1. Guest

    I read some old posts, they did this task in very different ways. How
    is the following one?

    Thank you for your time.


    /
    *******************************************************************************
    * Count the bit set in an integer. eg. integer: 0x01101011, bitcount:
    5

    ******************************************************************************/

    int bitcount(int i)
    {
    unsigned int cnt = 0, MASK;

    for (MASK = 0x1; MASK != 0; MASK <<= 1)
    if ((MASK & i) == MASK)
    cnt++;
    return cnt;
    }
     
    , Nov 5, 2007
    #1
    1. Advertising

  2. Richard Guest

    "" <> writes:

    > I read some old posts, they did this task in very different ways. How
    > is the following one?
    >
    > Thank you for your time.
    >
    >
    > /
    > *******************************************************************************
    > * Count the bit set in an integer. eg. integer: 0x01101011, bitcount:
    > 5
    >
    > ******************************************************************************/
    >
    > int bitcount(int i)
    > {
    > unsigned int cnt = 0, MASK;
    >
    > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > if ((MASK & i) == MASK)
    > cnt++;
    > return cnt;
    > }


    Someone else will tell you about left shifting out of range ( I reckon
    its probably fine with an unsigned int) but I would remove the
    comparison to MASK and put MASK in lower case since upper case tends to
    indicate a constant/#define.
     
    Richard, Nov 5, 2007
    #2
    1. Advertising

  3. Mark Bluemel Guest

    wrote:
    > I read some old posts, they did this task in very different ways. How
    > is the following one?
    > /*
    > * Count the bit set in an integer. eg. integer: 0x01101011, bitcount: 5
    > */
    >
    > int bitcount(int i)
    > {
    > unsigned int cnt = 0, MASK;
    >
    > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > if ((MASK & i) == MASK)
    > cnt++;
    > return cnt;
    > }


    Leaving aside the problems of reading this code aloud (I used to be a
    trainer and I know the pitfalls of a variable called "cnt")...

    Why do we need so many shifts? You need (sizeof int) * CHAR_BITS shifts
    even if there are no bits set in i.

    At the least, this may be less wasteful... (untested)

    int bitcount(unsigned int i) /* don't you want it unsigned? */
    {
    unsigned int cnt = 0;
    while(i) {
    cnt += i & 1;
    i >>= 1;
    }
    return cnt;
    }

    Seems equivalent to (but more verbose than)
    http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

    That webpage then looks at other techniques...
     
    Mark Bluemel, Nov 5, 2007
    #3
  4. Richard Bos Guest

    Richard <> wrote:

    > "" <> writes:
    >
    > > int bitcount(int i)
    > > {
    > > unsigned int cnt = 0, MASK;
    > >
    > > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > > if ((MASK & i) == MASK)
    > > cnt++;
    > > return cnt;
    > > }

    >
    > Someone else will tell you about left shifting out of range ( I reckon
    > its probably fine with an unsigned int)


    Where bitwise operations are concerned, never reckon, make sure. They're
    nasty, surprising bastards that will bite you sooner or later if you
    don't. In this case, though, I'm sure you reckoned correctly.

    > but I would remove the comparison to MASK


    Yes; it's an optimisation that I wouldn't expect even a good optimiser
    to get automatically.

    > and put MASK in lower case since upper case tends to indicate a
    > constant/#define.


    I agree.

    Richard
     
    Richard Bos, Nov 5, 2007
    #4
  5. Richard Guest

    (Richard Bos) writes:

    > Richard <> wrote:
    >
    >> "" <> writes:
    >>
    >> > int bitcount(int i)
    >> > {
    >> > unsigned int cnt = 0, MASK;
    >> >
    >> > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    >> > if ((MASK & i) == MASK)
    >> > cnt++;
    >> > return cnt;
    >> > }

    >>
    >> Someone else will tell you about left shifting out of range ( I reckon
    >> its probably fine with an unsigned int)

    >
    > Where bitwise operations are concerned, never reckon, make sure. They're
    > nasty, surprising bastards that will bite you sooner or later if you
    > don't. In this case, though, I'm sure you reckoned correctly.
    >
    >> but I would remove the comparison to MASK

    >
    > Yes; it's an optimisation that I wouldn't expect even a good optimiser
    > to get automatically.
    >
    >> and put MASK in lower case since upper case tends to indicate a
    >> constant/#define.

    >
    > I agree.
    >
    > Richard


    Although I did forget to suggest the "reduced bit check" which Mark
    correctly diagnosed.
     
    Richard, Nov 5, 2007
    #5
  6. Guest

    On Nov 5, 11:54 pm, Mark Bluemel <> wrote:
    > wrote:
    > > I read some old posts, they did this task in very different ways. How
    > > is the following one?
    > > /*
    > > * Count the bit set in an integer. eg. integer: 0x01101011, bitcount: 5
    > > */

    >
    > > int bitcount(int i)
    > > {
    > > unsigned int cnt = 0, MASK;

    >
    > > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > > if ((MASK & i) == MASK)
    > > cnt++;
    > > return cnt;
    > > }

    >
    > Leaving aside the problems of reading this code aloud (I used to be a
    > trainer and I know the pitfalls of a variable called "cnt")...
    >
    > Why do we need so many shifts? You need (sizeof int) * CHAR_BITS shifts
    > even if there are no bits set in i.
    >
    > At the least, this may be less wasteful... (untested)
    >


    Thank you.

    But my version may do less addition operation. Is addition operation
    more wasteful than if's?

    > int bitcount(unsigned int i) /* don't you want it unsigned? */
    > {
    > unsigned int cnt = 0;
    > while(i) {
    > cnt += i & 1;
    > i >>= 1;
    > }
    > return cnt;
    > }
    >
    > Seems equivalent to (but more verbose than)http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
    >
    > That webpage then looks at other techniques...
     
    , Nov 5, 2007
    #6
  7. In article <>,
    <> wrote:

    >But my version may do less addition operation. Is addition operation
    >more wasteful than if's?


    It depends not only on the instruction set architecture but also
    on the exact processor revision, and it depends upon the surrounding
    code.

    Historically, 'if' was noticably more expensive than addition,
    but processors have become pretty smart to reduce the difference;
    some have "move conditional" instructions, some will
    internally start working on two "hypothetical" cases simultaneously
    of the branch happening or not happening and will discard the
    unneeded hypothesis when the condition is fully evaluated
    (which is harder than it sounds because it has to hold on to
    exceptions, supressing any exceptions that didn't "really" occur
    but allowing the exceptions for the hypothetical side that got
    realized.)
    --
    "I was very young in those days, but I was also rather dim."
    -- Christopher Priest
     
    Walter Roberson, Nov 5, 2007
    #7
  8. pete Guest

    wrote:
    >
    > On Nov 5, 11:54 pm, Mark Bluemel <> wrote:
    > > wrote:


    > > > is the following one?
    > > > /*
    > > > * Count the bit set in an integer.
    > > > eg. integer: 0x01101011, bitcount: 5
    > > > */

    > >
    > > > int bitcount(int i)
    > > > {
    > > > unsigned int cnt = 0, MASK;

    > >
    > > > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > > > if ((MASK & i) == MASK)


    (i) is the wrong type. It should be unsigned.
    If (i) has a value of (-1), then how many bits are set in (i)
    depends on which of three representations is used,
    but bitcount will always return the number of bits
    used by two's complement representation.

    > > > cnt++;
    > > > return cnt;
    > > > }

    > >
    > > Leaving aside the problems of reading this code aloud
    > > (I used to be a
    > > trainer and I know the pitfalls of a variable called "cnt")...
    > >
    > > Why do we need so many shifts?
    > > You need (sizeof int) * CHAR_BITS shifts
    > > even if there are no bits set in i.
    > >
    > > At the least, this may be less wasteful... (untested)
    > >

    >
    > Thank you.
    >
    > But my version may do less addition operation. Is addition operation
    > more wasteful than if's?


    The last time that I was looking cpu's was in the 1990's.
    At that time, typically, a conditional jump
    took about twice as long as an integer addition operation.

    By every metric I know for guessing how fast a function will be,
    bit_count should be faster than bitcount.

    unsigned bit_count(unsigned n)
    {
    unsigned count;

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

    --
    pete
     
    pete, Nov 5, 2007
    #8
  9. On Nov 5, 9:18 pm, pete <> wrote:

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


    What's much more interesting is a _fast_ implementation of the
    following:

    /* Return the number of bits set n consecutive ints */
    unsigned long array_bitcount (unsigned int* p, unsigned long
    number_of_ints)
    {
    unsigned long count, i;
    for (i = 0, count = 0; i < number_of_ints; ++i)
    count += bit_count (p );
    }
     
    christian.bau, Nov 5, 2007
    #9
  10. Ben Pfaff Guest

    "" <> writes:

    > int bitcount(int i)
    > {
    > unsigned int cnt = 0, MASK;
    >
    > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > if ((MASK & i) == MASK)
    > cnt++;
    > return cnt;
    > }


    I have timed the following in the past as being quite fast. It
    is branch-free:

    /* Compute and return the the number of 1-bits set in X. */
    int
    count_one_bits_32 (uint32_t x)
    {
    x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
    x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
    x = (x >> 16) + (x & 0xffff);
    x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
    return (x >> 8) + (x & 0x00ff);
    }

    --
    "I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz
     
    Ben Pfaff, Nov 5, 2007
    #10
  11. James Harris Guest

    On 5 Nov, 15:33, ""
    <> wrote:
    > I read some old posts, they did this task in very different ways. How
    > is the following one?
    >
    > Thank you for your time.
    >
    > /
    > ***************************************************************************­****
    > * Count the bit set in an integer. eg. integer: 0x01101011, bitcount:
    > 5
    >
    > ***************************************************************************­***/
    >
    > int bitcount(int i)
    > {
    > unsigned int cnt = 0, MASK;
    >
    > for (MASK = 0x1; MASK != 0; MASK <<= 1)
    > if ((MASK & i) == MASK)
    > cnt++;
    > return cnt;


    Since others are going for speed how about the following. (The C may
    not be completely correct.) It combines fast lookup with a small
    table. There is a reasonable chance that the looked up value will be
    in cache (which would be better if there were some way to align the
    array).

    int nibble_bits[] = { /* The number of bits in each nibble 0 to 15 */
    0, 1, 1, 2, 1, 2, 2, 3,
    1, 2, 2, 3, 2, 3, 3, 4
    }

    int bitcount (int i) {
    int bits_set = 0;

    for (; i; i >>= 4) {
    bits_set += nibble_bits[i & 0xf];
    }
    return bits_set;
    }
     
    James Harris, Nov 5, 2007
    #11
  12. Ark Khasin Guest

    Ben Pfaff wrote:

    > I have timed the following in the past as being quite fast. It
    > is branch-free:
    >
    > /* Compute and return the the number of 1-bits set in X. */
    > int
    > count_one_bits_32 (uint32_t x)
    > {
    > x = ((x & 0xaaaaaaaaU) >> 1) + (x & 0x55555555U);
    > x = ((x & 0xccccccccU) >> 2) + (x & 0x33333333U);
    > x = (x >> 16) + (x & 0xffff);
    > x = ((x & 0xf0f0) >> 4) + (x & 0x0f0f);
    > return (x >> 8) + (x & 0x00ff);
    > }
    >


    Just for kicks, here's yet another size-specific (and also
    generalizable) version. Here multiplication does bit tallying in pruned
    bitmaps.
    Whether it's better or worse probably depends on the instruction set.
    #define ONES 0x11111111U
    unsigned mybits(uint32_t x)
    {
    unsigned count;
    count = ((x & ONES) * ONES) >> 28;
    count += (((x>>1) & ONES) * ONES) >> 28;
    count += (((x>>2) & ONES) * ONES) >> 28;
    count += (((x>>3) & ONES) * ONES) >> 28;
    return count;
    }

    --
    Ark
     
    Ark Khasin, Nov 6, 2007
    #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. Charles Hixson

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    5
    Views:
    238
    Charles Hixson
    Oct 26, 2012
  2. MRAB
    Replies:
    0
    Views:
    164
  3. Steven D'Aprano

    Re: bit count or bit set && Python3

    Steven D'Aprano, Oct 25, 2012, in forum: Python
    Replies:
    12
    Views:
    284
    Neil Cerutti
    Oct 26, 2012
  4. Mark Lawrence

    Re: bit count or bit set && Python3

    Mark Lawrence, Oct 25, 2012, in forum: Python
    Replies:
    0
    Views:
    159
    Mark Lawrence
    Oct 25, 2012
  5. Charles Hixson

    bit count or bit set && Python3

    Charles Hixson, Oct 25, 2012, in forum: Python
    Replies:
    0
    Views:
    113
    Charles Hixson
    Oct 25, 2012
Loading...

Share This Page