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

Discussion in 'C Programming' started by Cuthbert, Sep 12, 2006.

1. ### CuthbertGuest

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

Cuthbert, Sep 12, 2006

2. ### T.M. SommersGuest

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

T.M. Sommers, Sep 12, 2006

3. ### Frederick GothamGuest

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

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

Frederick Gotham, Sep 12, 2006
4. ### Ancient_HackerGuest

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.

Ancient_Hacker, Sep 12, 2006
5. ### Walter RobersonGuest

In article <>,
Ancient_Hacker <> 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)

Walter Roberson, Sep 12, 2006
6. ### James McGillGuest

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/~seander/bithacks.html#CountBitsSetNaive

James McGill, Sep 12, 2006
7. ### Richard HeathfieldGuest

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)

Richard Heathfield, Sep 12, 2006
8. ### SkarmanderGuest

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.

Skarmander, Sep 12, 2006
9. ### Julian V. NobleGuest

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

Julian V. Noble, Sep 12, 2006
10. ### peteGuest

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

pete, Sep 13, 2006
11. ### kondalGuest

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

There is a faster program easy to remember and i.e x&=(x-1) and doesn't
require any storage requirements. Here is the program

int main(void)
{
x = 0xFF0F;
int n = 0;

while(x)
{
x &= (x-1)
n++;
}

printf("No of bits = %d\n", n);
}

The worst case for the loop would be when all the bits are set.
Actually for each iteration the statement x=x&(x-1) would remove one
bit. Just check it out manually.

There is even better and faster algorithm but difficult to remember.

int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
return n % 255 ;
}

I got this algorithm from my old book, hard to remember (atleast for me)

kondal, Sep 13, 2006
12. ### jaysomeGuest

On 12 Sep 2006 13:48:55 -0700, "Ancient_Hacker" <>
wrote:

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

On the TI 5501 DSP I'm currently working with, where sizeof(int) == 1
and CHAR_BIT == 16 (and the byte ordering is Big Endian, to boot), I'm
skeptical that this would work.

Use of a lookup table could easily result in exceeding the size of my
available EEPROM that stores my program memory (and that assumes that
you constructed the table with a priori knowledge that CHAR_BIT ==
16).

the cache.

STD_FILE: std_5501.lnt
PC-lint for C/C++ (NT) Vers. 8.00u, Copyright Gimpel Software
1985-2006

--- Module: bits.c (C)
_
int var = 0xFF0F;
bits.c(3) : Warning 569: Loss of information (initialization) (16 bits
to 15 bits)
_
for ( i = 0; i < sizeof(int)*8 ; i++ )
bits.c(6) : Warning 574: Signed-unsigned mix with relational
_
{ count += var & 1; var >>= 1; }
bits.c(7) : Info 702: Shift right of signed quantity (int)
_
printf("%d\n", count);
bits.c(9) : Info 718: Symbol 'printf' undeclared, assumed to return
int
bits.c(9) : Info 746: call to function 'printf()' not made in the
presence of a prototype

/// Start of Pass 2 ///

--- Module: bits.c (C)

--- Global Wrap-up

Note 900: Successful completion, 5 messages produced
Tool returned code: 0

Regards
--
jay

jaysome, Sep 13, 2006
13. ### russell kym horsellGuest

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?

There are a couple.

E.g. when you take the 2's complement of a number, you do not complement
the lowest-order-bit. Using (-x)&x is therefore a way of "skiiping to
the next bit that's set" rather than having to go through bit positions
1 at a time -- 1/2 the time finding a 0.

Then there's the mysterious method that relies on carry in 2s complement
allowing you to "count" the 1's directly.
It's a recursive method (which you later can flatten out for particular
sizes of your compiuter's native word) based on the idea "how many bits
are set in a 2 bit quantity b1b2". To find out how many in this 2-bit
problem, you want to add b1 and b2. I.e. (x&1)+((x>>1)&1).

Now, what if we have (say) 4 bits b1b2b3b4? We can use
(x&5)+((x>>1)&5) to get [sum b1,b2][sum b3,b4] -- i.e. 2 x 2-bit quantities,
and then use
(x&3)+((x>>2)&3) to convert that to [sum b1,b2,b3,b4].

Just build up logically, as the old short story said.

russell kym horsell, Sep 13, 2006
14. ### Richard HeathfieldGuest

kondal said:

<snip>

> There is even better and faster algorithm but difficult to remember.
>
>
> int bitcount (unsigned int n)
> {
> n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
> n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
> n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
> return n % 255 ;
> }

What makes you think this is faster? And what happens when the code is
ported to a platform with 64-bit unsigned ints?

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

Richard Heathfield, Sep 13, 2006
15. ### kondalGuest

Richard Heathfield wrote:
> kondal said:
>
> <snip>
>
> > There is even better and faster algorithm but difficult to remember.
> >
> > #define MASK_01010101 (((unsigned int)(-1))/3)
> > #define MASK_00110011 (((unsigned int)(-1))/5)
> > #define MASK_00001111 (((unsigned int)(-1))/17)
> >
> > int bitcount (unsigned int n)
> > {
> > n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
> > n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
> > n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
> > return n % 255 ;
> > }

>
> What makes you think this is faster? And what happens when the code is
> ported to a platform with 64-bit unsigned ints?
>
> --
> 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)

There is no loop here to check and no of clock cycles to be executed
would be fas less than my previous algorithm.

Here is the program for 64 bits

int bitcount (unsigned int n)
{
n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
n = (n & MASK_00111100) + ((n >> 8) & MASK_00111100) ;
return n % 255 ;
}

-kondal

kondal, Sep 13, 2006
16. ### kondalGuest

kondal wrote:
>
>
> int bitcount (unsigned int n)
> {
> n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
> n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
> n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
> n = (n & MASK_00111100) + ((n >> 8) & MASK_00111100) ;
> return n % 255 ;
> }

Sorry I forgot, 'unsigned int' should be replaced by to 'unsigned long
long int'

-kondal

kondal, Sep 13, 2006
17. ### Richard HeathfieldGuest

kondal said:

> Richard Heathfield wrote:
>> kondal said:
>>
>> <snip>
>>
>> > There is even better and faster algorithm but difficult to remember.
>> >
>> > #define MASK_01010101 (((unsigned int)(-1))/3)
>> > #define MASK_00110011 (((unsigned int)(-1))/5)
>> > #define MASK_00001111 (((unsigned int)(-1))/17)
>> >
>> > int bitcount (unsigned int n)
>> > {
>> > n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
>> > n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
>> > n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
>> > return n % 255 ;
>> > }

>>
>> What makes you think this is faster? And what happens when the code is
>> ported to a platform with 64-bit unsigned ints?
>>

<snip>
>
> Here is the program for 64 bits
>
>
> int bitcount (unsigned int n)
> {
> n = (n & MASK_01010101) + ((n >> 1) & MASK_01010101) ;
> n = (n & MASK_00110011) + ((n >> 2) & MASK_00110011) ;
> n = (n & MASK_00001111) + ((n >> 4) & MASK_00001111) ;
> n = (n & MASK_00111100) + ((n >> 8) & MASK_00111100) ;
> return n % 255 ;
> }

What happens when the code is ported to a platform with 180-bit ints?

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

Richard Heathfield, Sep 13, 2006
18. ### Frederick GothamGuest

Richard Heathfield posted:

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

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

I meant something more along the following lines. Do compilers nowadays
optimise away Bitwise-AND operations when one of the operands is known to
be 0 at compile-time?

/* Macro: QUANT_BITS_SET

This macro determines the quantity of bits which
are set in an integer expression whose signedness
is unsigned.

The typedef, "BitsSetType", specifies the unsigned
integer type which is to be used for processing.

Before processing takes place, the argument is
converted to BitsSetType.

This macro should work with unsigned integer types
as wide as 1024 bits.

NB: This macro evaluates its argument more than once.
*/

typedef unsigned BitsSetType;

#define IMAX_BITS(m) (\
(m) /((m)%0x3fffffffL+1) /0x3fffffffL \
%0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 \
+ 4 \
- 12 / ((m)%31+3) )

shift_left_by < IMAX_BITS((BitsSetType)-1) \
? (BitsSetType)1 << shift_left_by \
: (BitsSetType)0 )

#define QUANT_BITS_SET_RAW(x) (\
!!((x)&(BitsSetType)1) + !!((x)&(BitsSetType)1<<1) \
+!!((x)&(BitsSetType)1<<2) + !!((x)&(BitsSetType)1<<3) \
+!!((x)&(BitsSetType)1<<4) + !!((x)&(BitsSetType)1<<5) \
+!!((x)&(BitsSetType)1<<6) + !!((x)&(BitsSetType)1<<7) \
+!!((x)&(BitsSetType)1<<8) + !!((x)&(BitsSetType)1<<9) \
+!!((x)&(BitsSetType)1<<10) +!!((x)&(BitsSetType)1<<11) \
+!!((x)&(BitsSetType)1<<12) +!!((x)&(BitsSetType)1<<13) \
+!!((x)&(BitsSetType)1<<14) +!!((x)&(BitsSetType)1<<15) \

#define QUANT_BITS_SET(x) QUANT_BITS_SET_RAW( ((BitsSetType)(x)) )

#include <stdio.h>

int main(void)
{
/* Let's make an array of length 4 */

int arr[QUANT_BITS_SET(17)];

printf("%u",(unsigned)(sizeof arr/sizeof*arr));
}

The codes prints 2 on my system, but you get the idea...

--

Frederick Gotham

Frederick Gotham, Sep 13, 2006
19. ### SkarmanderGuest

Frederick Gotham wrote:
> Richard Heathfield posted:
>
>> 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.

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

>
>
> I meant something more along the following lines. Do compilers nowadays
> optimise away Bitwise-AND operations when one of the operands is known to
> be 0 at compile-time?
>

Yes. Constant folding is somethings almost all compilers handle well. (Those
that don't are usually too hopeless to consider for optmizing purposes.)
Take care that the compiler still has to parse the entire expression; some
low-end systems may barf on such enormous constructs.

> /* Macro: QUANT_BITS_SET
>
> This macro determines the quantity of bits which
> are set in an integer expression whose signedness
> is unsigned.
>

I prefer my desktop calculator, but YMMV.

<snip>
> /* Let's make an array of length 4 */
>

A misleading comment if ever I saw one.

> int arr[QUANT_BITS_SET(17)];
>

Hmm, I'd write that

#define BITS_SET_IN_THE_BINARY_REPRESENTATION_OF_17 2
[...]
int arr[BITS_SET_IN_THE_BINARY_REPRESENTATION_OF_17]

Still uses a rather unwieldy macro, but it's a tad shorter nonetheless.

> printf("%u",(unsigned)(sizeof arr/sizeof*arr));
> }
>
> The codes prints 2 on my system, but you get the idea...
>

Yes, the preprocessor is neat.

S.

Skarmander, Sep 14, 2006
20. ### Frederick GothamGuest

Skarmander posted:

> Constant folding is somethings almost all compilers handle well. (Those
> that don't are usually too hopeless to consider for optmizing
> purposes.)

We could always write more macros which use the ternary operator to get rid
of redundant Bitwise-AND operations. Something like:

: 0 )

And we could even go further to strip out the additions:

(b) \
? (a) + (b) \
: (a) )

>> /* Let's make an array of length 4 */
>>

> A misleading comment if ever I saw one.

Don't ask me how, but I somehow calculated that 17 had four bits set.

--

Frederick Gotham

Frederick Gotham, Sep 14, 2006