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]

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ites:

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]

lovecreatesbea. [e-mail] 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(unsign ed 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/~seande...ntBitsSetNaive

That webpage then looks at other techniques...

[Richard Bos]

Richard <rg****@gmail.c omwrote:

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ites:

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]

rl*@hoekstra-uitgeverij.nl (Richard Bos) writes:

Richard <rg****@gmail.c omwrote:

>"lovecreatesbe [e-mail]" <lo************ ***@gmail.comwr ites:

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.

[lovecreatesbea...]

On Nov 5, 11:54 pm, Mark Bluemel <mark_blue...@p obox.comwrote:

lovecreatesbea. [e-mail] 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(unsign ed 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/~seande...ntBitsSetNaive

That webpage then looks at other techniques...

[Walter Roberson]

In article <11************ **********@i13g 2000prf.googleg roups.com>,
lovecreatesbea. [e-mail] <lo************ ***@gmail.comwr ote:

>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 "hypothetic al" 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

[pete]

lovecreatesbea. [e-mail] wrote:

>
On Nov 5, 11:54 pm, Mark Bluemel <mark_blue...@p obox.comwrote:

lovecreatesbea. [e-mail] 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(unsig ned n)
{
unsigned count;

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

--
pete

[christian.bau]

On Nov 5, 9:18 pm, pete <pfil...@mindsp ring.comwrote:

unsigned bit_count(unsig ned 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 [i]);
}

[Ben Pfaff]

"lovecreatesbea [e-mail]" <lo************ ***@gmail.comwr ites:

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