Bit count of an integer

[lovecreatesbea...]

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;
}

 

[Richard]

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.

 

[Mark Bluemel]

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

 

[Richard Bos]

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]

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.


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


I agree.

Richard

Although I did forget to suggest the "reduced bit check" which Mark
correctly diagnosed.

 

[lovecreatesbea...]

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?

 

[Walter Roberson]

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

 

[pete]

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

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;
}

 

[christian.bau]

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 );
}

 

[Ben Pfaff]

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);
}

 

[James Harris]

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;
}

 

[Ark Khasin]

> 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;
}