Velocity Reviews > Bit count of an integer

# Bit count of an integer

lovecreatesbea...@gmail.com
Guest
Posts: n/a

 11-05-2007
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;

cnt++;
return cnt;
}

Richard
Guest
Posts: n/a

 11-05-2007
"(E-Mail Removed)" <(E-Mail Removed)> 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;
>
> 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
Guest
Posts: n/a

 11-05-2007
(E-Mail Removed) 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;
>
> 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/~seande...ntBitsSetNaive

That webpage then looks at other techniques...

Richard Bos
Guest
Posts: n/a

 11-05-2007
Richard <(E-Mail Removed)> wrote:

> "(E-Mail Removed)" <(E-Mail Removed)> writes:
>
> > int bitcount(int i)
> > {
> > unsigned int cnt = 0, 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
Guest
Posts: n/a

 11-05-2007
http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Bos) writes:

> Richard <(E-Mail Removed)> wrote:
>
>> "(E-Mail Removed)" <(E-Mail Removed)> writes:
>>
>> > int bitcount(int i)
>> > {
>> > unsigned int cnt = 0, 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...@gmail.com
Guest
Posts: n/a

 11-05-2007
On Nov 5, 11:54 pm, Mark Bluemel <(E-Mail Removed)> wrote:
> (E-Mail Removed) 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;

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

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/~seande...ntBitsSetNaive
>
> That webpage then looks at other techniques...

Walter Roberson
Guest
Posts: n/a

 11-05-2007
In article <(E-Mail Removed) .com>,
(E-Mail Removed) <(E-Mail Removed)> wrote:

>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

pete
Guest
Posts: n/a

 11-05-2007
(E-Mail Removed) wrote:
>
> On Nov 5, 11:54 pm, Mark Bluemel <(E-Mail Removed)> wrote:
> > (E-Mail Removed) 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;

> >

(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

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

christian.bau
Guest
Posts: n/a

 11-05-2007
On Nov 5, 9:18 pm, pete <(E-Mail Removed)> 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 [i]);
}

Ben Pfaff
Guest
Posts: n/a

 11-05-2007
"(E-Mail Removed)" <(E-Mail Removed)> writes:

> int bitcount(int i)
> {
> unsigned int cnt = 0, 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 >> + (x & 0x00ff);
}

--
"I ran it on my DeathStation 9000 and demons flew out of my nose." --Kaz