473,902 Members | 3,411 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
34 11354

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)
{
return n % 255 ;
}

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

Sep 13 '06 #11
On 12 Sep 2006 13:48:55 -0700, "Ancient_Hacker " <gr**@comcast.n et>
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
Sep 13 '06 #12
Cuthbert <cu**********@g mail.comwrote:
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. :)
Sep 13 '06 #13
kondal said:

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

int bitcount (unsigned int n)
{
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)
Sep 13 '06 #14
Richard Heathfield wrote:
kondal said:

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

int bitcount (unsigned int n)
{
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)
{
return n % 255 ;
}

-kondal

Sep 13 '06 #15
kondal wrote:
>

int bitcount (unsigned int n)
{
return n % 255 ;
}
Sorry I forgot, 'unsigned int' should be replaced by to 'unsigned long
long int'

-kondal

Sep 13 '06 #16
kondal said:
Richard Heathfield wrote:
>kondal said:

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

int bitcount (unsigned int n)
{
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)
{
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)
Sep 13 '06 #17
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, "BitsSetTyp e", 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)%0x3fffffff L+1) /0x3fffffffL \
%0x3fffffffL *30 \
+ (m)%0x3fffffffL /((m)%31+1)/31%31*5 \
+ 4 \
- 12 / ((m)%31+3) )

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

#define QUANT_BITS_SET_ RAW(x) (\
!!((x)&(BitsSet Type)1) + !!((x)&(BitsSet Type)1<<1) \
+!!((x)&(BitsSe tType)1<<2) + !!((x)&(BitsSet Type)1<<3) \
+!!((x)&(BitsSe tType)1<<4) + !!((x)&(BitsSet Type)1<<5) \
+!!((x)&(BitsSe tType)1<<6) + !!((x)&(BitsSet Type)1<<7) \
+!!((x)&(BitsSe tType)1<<8) + !!((x)&(BitsSet Type)1<<9) \
+!!((x)&(BitsSe tType)1<<10) +!!((x)&(BitsSe tType)1<<11) \
+!!((x)&(BitsSe tType)1<<12) +!!((x)&(BitsSe tType)1<<13) \
+!!((x)&(BitsSe tType)1<<14) +!!((x)&(BitsSe tType)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",(un signed)(sizeof arr/sizeof*arr));
}

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

--

Frederick Gotham
Sep 13 '06 #18
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_REPRESE NTATION_OF_17 2
[...]
int arr[BITS_SET_IN_THE _BINARY_REPRESE NTATION_OF_17]

Still uses a rather unwieldy macro, but it's a tad shorter nonetheless.
printf("%u",(un signed)(sizeof arr/sizeof*arr));
}

The codes prints 2 on my system, but you get the idea...
Yes, the preprocessor is neat.

S.
Sep 14 '06 #19
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:

#define BitwiseAND(x,ma sk) (\
: 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
Sep 14 '06 #20

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