473,890 Members | 1,430 Online

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

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

Sep 12 '06 #1
34 11350
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 -- tm*@nj.net -- AB2SB

Sep 12 '06 #2
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<<8) + !!((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<<18) + !!((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 8)

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
Sep 12 '06 #3

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.

Sep 12 '06 #4
In article <11************ **********@d34g 2000cwd.googleg roups.com>,
Ancient_Hacker <gr**@comcast.n etwrote:
>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)
Sep 12 '06 #5
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
Sep 12 '06 #6
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<<8) + !!((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<<18) + !!((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)
Sep 12 '06 #7
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.
Sep 12 '06 #8
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
Sep 12 '06 #9
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(unsig ned n);

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

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

unsigned bit_count(unsig ned n)
{
unsigned count;

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

/* END new.c */
--
pete
Sep 12 '06 #10

This thread has been closed and replies have been disabled. Please start a new discussion.