Velocity Reviews > How many bits are '1' in a integer variable?

# How many bits are '1' in a integer variable?

Cuthbert
Guest
Posts: n/a

 09-12-2006
Hi folks,

I am trying to find a more efficient way to count "How many bits are
'1' in a integer variable?".

I still have no idea to count the bits except using a loop and "if"
statements.
Could you know any other more efficient way?

Cuthbert

int main (void)
{
int var = 0xFF0F;
int i, count = 0;
for ( i = 0; i < sizeof(int)*8 ; i++ )
if ( mask<<i & var) count++ ;

printf("%d\n", count);

return 0;
}

T.M. Sommers
Guest
Posts: n/a

 09-12-2006
Cuthbert wrote:
> Hi folks,
>
> I am trying to find a more efficient way to count "How many bits are
> '1' in a integer variable?".
>
> I still have no idea to count the bits except using a loop and "if"
> statements.
> Could you know any other more efficient way?

Break the int into bytes and use a lookup table.

--
Thomas M. Sommers -- http://www.velocityreviews.com/forums/(E-Mail Removed) -- AB2SB

Frederick Gotham
Guest
Posts: n/a

 09-12-2006
T.M. Sommers posted:

> Cuthbert wrote:
>> Hi folks,
>>
>> I am trying to find a more efficient way to count "How many bits are
>> '1' in a integer variable?".
>>
>> I still have no idea to count the bits except using a loop and "if"
>> statements.
>> Could you know any other more efficient way?

>
> Break the int into bytes and use a lookup table.

I'm sure there's a better way than that... perhaps even an expression
yielding a compile-time constant. Maybe something like:

#define UINT_BITS_SET(x)\
!!((x)&1U) + !!((x)&1U<<1) + !!((x)&1U<<2) + !!((x)&1U<<3)\
+ !!((x)&1U<<4) + !!((x)&1U<<5) + !!((x)&1U<<6) + !!((x)&1U<<7)\
+ !!((x)&1U<< + !!((x)&1U<<9) + !!((x)&1U<<10) + !!((x)&1U<<11)\
+ !!((x)&1U<<12) + !!((x)&1U<<13) + !!((x)&1U<<14) + !!((x)&1U<<15)\
+ !!((x)&1U<<16) + !!((x)&1U<<17) + !!((x)&1U<<1 + !!((x)&1U<<19)\
+ !!((x)&1U<<20)

I'm not sure if it's undefined behaviour to left shift an unsigned int by
more places than it has bits; if not, then you can simply go as high as you
want:

+ !!((x)&1U<<6354

If it is however, then you could use the IMAX_BITS macro in conjunction
with the modulus and division operators to keep things safe.

--

Frederick Gotham

Ancient_Hacker
Guest
Posts: n/a

 09-12-2006

Cuthbert wrote:
> Hi folks,
>

a bit simpler and therefore perhaps somewhat faster:

int main (void)
{
int var = 0xFF0F;
int i, count = 0;

for ( i = 0; i < sizeof(int)*8 ; i++ )
{ count += var & 1; var >>= 1; }

printf("%d\n", count);

return 0;
}

a byte lookup table might or might not be faster, depending on what
happens with the cache.

Walter Roberson
Guest
Posts: n/a

 09-12-2006
In article <(E-Mail Removed) .com>,
Ancient_Hacker <(E-Mail Removed)> wrote:

>Cuthbert wrote:
>> Hi folks,

Please quote enough context so that people know what is being discussed.
In this case it is counting the number of 1 bits in an integer variable.

>a bit simpler and therefore perhaps somewhat faster:

>int main (void)
>{
> int var = 0xFF0F;
> int i, count = 0;

> for ( i = 0; i < sizeof(int)*8 ; i++ )
> { count += var & 1; var >>= 1; }

> printf("%d\n", count);
>
> return 0;
>}

Why sizeof(int)*8 ?

It appears to me that you have assumed CHAR_BIT to be 8.
--
"law -- it's a commodity"
-- Andrew Ryan (The Globe and Mail, 2005/11/26)

James McGill
Guest
Posts: n/a

 09-12-2006
Ancient_Hacker wrote:

> a byte lookup table might or might not be faster, depending on what
> happens with the cache.

My favorite approach that I've seen to this (Homework) problem involved
a combination of table lookup (for all the 4-bit unch ofcombinations)
and a series of shifts.

Pretty good compromise.

Here are a few different ways to do it.
http://graphics.stanford.edu/~seande...ntBitsSetNaive

Richard Heathfield
Guest
Posts: n/a

 09-12-2006
Frederick Gotham said:

> T.M. Sommers posted:
>
>> Cuthbert wrote:
>>> Hi folks,
>>>
>>> I am trying to find a more efficient way to count "How many bits are
>>> '1' in a integer variable?".
>>>
>>> I still have no idea to count the bits except using a loop and "if"
>>> statements.
>>> Could you know any other more efficient way?

>>
>> Break the int into bytes and use a lookup table.

>
>
> I'm sure there's a better way than that... perhaps even an expression
> yielding a compile-time constant. Maybe something like:
>
>
> #define UINT_BITS_SET(x)\
> !!((x)&1U) + !!((x)&1U<<1) + !!((x)&1U<<2) + !!((x)&1U<<3)\
> + !!((x)&1U<<4) + !!((x)&1U<<5) + !!((x)&1U<<6) + !!((x)&1U<<7)\
> + !!((x)&1U<< + !!((x)&1U<<9) + !!((x)&1U<<10) + !!((x)&1U<<11)\
> + !!((x)&1U<<12) + !!((x)&1U<<13) + !!((x)&1U<<14) + !!((x)&1U<<15)\
> + !!((x)&1U<<16) + !!((x)&1U<<17) + !!((x)&1U<<1 + !!((x)&1U<<19)\
> + !!((x)&1U<<20)

I'm not convinced that's a better way than:

unsigned int count_set_bits(unsigned long n)
{
unsigned int set_bits[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4
};
unsigned int count = 0;
while(n > 0)
{
count += set_bits[n & 0xf];
n >>= 4;
}
return count;
}

Your solution doesn't appear to cope with integers wider than 21 bits, for a
start. Secondly, it doesn't cope with integers that are /fewer/ than 21
bits wide! Thirdly, it could conceivably be counting "padding bits", bits
that do not contribute to the value of the integer.

> I'm not sure if it's undefined behaviour to left shift an unsigned int by
> more places than it has bits; if not, then you can simply go as high as
> you want:

Quoth 3.3.7 of C90: "The integral promotions are performed on each of the
operands. The type of the result is that of the promoted left operand. If
the value of the right operand is negative or is greater than or equal to
the width in bits of the promoted left operand, the behavior is undefined."

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

Skarmander
Guest
Posts: n/a

 09-12-2006
Cuthbert wrote:
> Hi folks,
>
> I am trying to find a more efficient way to count "How many bits are
> '1' in a integer variable?".
>

http://graphics.stanford.edu/~seander/bithacks.html

Pay close attention, though; most of these hacks assume integer sizes, two's
complement machines, or other things that may be quite justifiable, but
nevertheless render the code unportable.

S.

Julian V. Noble
Guest
Posts: n/a

 09-12-2006
Skarmander wrote:
> Cuthbert wrote:
>> Hi folks,
>>
>> I am trying to find a more efficient way to count "How many bits are
>> '1' in a integer variable?".
>>

> http://graphics.stanford.edu/~seander/bithacks.html
>
> Pay close attention, though; most of these hacks assume integer sizes,
> two's complement machines, or other things that may be quite
> justifiable, but nevertheless render the code unportable.
>
> S.

I believe many of these hacks are in "Hacker's Delight" by
Henry Warren. As is the answer to the OP's question.

--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia

pete
Guest
Posts: n/a

 09-12-2006
Cuthbert wrote:
>
> Hi folks,
>
> I am trying to find a more efficient way to count "How many bits are
> '1' in a integer variable?".
>
> I still have no idea to count the bits except using a loop and "if"
> statements.
> Could you know any other more efficient way?
>
> Cuthbert
>
> int main (void)
> {
> int var = 0xFF0F;
> int i, count = 0;
> for ( i = 0; i < sizeof(int)*8 ; i++ )
> if ( mask<<i & var) count++ ;
>
> printf("%d\n", count);
>
> return 0;
> }

/* BEGIN new.c */

#include <stdio.h>

unsigned bit_count(unsigned n);

int main (void)
{
unsigned var = 0xFF0F;
unsigned count = bit_count(var);

printf("%u\n", count);
return 0;
}

unsigned bit_count(unsigned n)
{
unsigned count;

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

/* END new.c */

--
pete