# Thread: How many bits are '1' in an integer variable?

1. Originally Posted by swoopy
Well maybe Prelude will post one then. Hopefully without a lookup table though. That kind of takes the fun out of it.
Well I hope he doesn't post the table!!!
Not sure what he intends to do, but I think the OP's program is about as good as it gets all things considered.

2. Originally Posted by Ken Fitlike
He cross-posted as Daved mentioned.
I didn't see that before I posted, anyway his code didn't look much like C++ to me
as I could understand it!!

3. For an entirely non-portable way:
Code:
```long binaryCount(long number)
{
number = (number & 0x55555555) + ((number & 0xaaaaaaaa) >> 1);
number = (number & 0x33333333) + ((number & 0xcccccccc) >> 2);
number = (number & 0x0f0f0f0f) + ((number & 0xf0f0f0f0) >> 4);
number = (number & 0x00ff00ff) + ((number & 0xff00ff00) >> 8);
return   (number & 0x0000ffff) + ((number & 0xffff0000) >> 16);
}```
That assumes 4 byte longs.

4. Code:
```int mask = ...;
int count;
asm("ctpop %1, %0" : "=r"(count) : "r"(mask));```
This will, of course, only compile with GCC on an Alpha machine, but hey, you wanted efficient, right? No one said anything about portable.

5. Boring I know, but what can you do?
Code:
```#include <stdio.h>

int
main (void)
{
unsigned int v = 0xFF0F;
unsigned int w = v - ((v >> 1) & 0x55555555);
unsigned int x = (w & 0x33333333) + ((w >> 2) & 0x33333333);
unsigned int c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
printf ("%d\n", c);
return 0;
}```
Whole bunch of 'em here
http://graphics.stanford.edu/~seander/bithacks.html

6. Damn it Salem. I get all the way to your post thinking "I've got a great link to post".

7. Originally Posted by esbo
I didn't see that before I posted, anyway his code didn't look much like C++ to me
as I could understand it!!
Yeah I bet that was a real feat.

Quzah.

8. Well you could change:-
Code:
```for ( i = 0; i < sizeof(int)*8 ; i++ )
if ( mask<<i & var) count++ ;```
to (to get rid of the 'if')
Code:
```for ( i = 0; i < sizeof(int)*8 ; i++ )
or even
Code:
`for ( i = 0; i < sizeof(int)*8 ; i++, count+= (mask& var>>i ));`

9. Nevermind. I'm slow today. All of these have already been covered probably, but if not, there ya go.

Quzah.

10. The fastest way I found is using lookup table. For integer, 4 bytes long, it takes 4 additional operators only.

And, this :
Code:
```for ( i = 0; i < sizeof(int)*8 ; i++ )
Also, great idea~!

Thanks a lot, folks.

====================

About the cross-posted, I posted this topic in C++ board first. It's wrong place for my target language, C. Then, I posted it in C board again. Sorry. Thank you, Ken Fitlike, for adding code tags.

11. You could even do this:
Code:
```int count_ones(unsigned int var)
{
int count = 0;
while (var != 0)
{
var >>= 1;
}
return count;
}```
I prefer the if so I'd do:
Code:
```int count_ones(unsigned int var)
{
int count = 0;
while (var != 0)
{
count++;
var >>= 1;
}
return count;
}```

12. I guess the fastest way would be really huge look up table, for a 32 bit int you would need
4 gigabites+ of memory though.
For a 64 bit int well, you might need a loan to buy the memory

The program might take a while to load but once loaded it would run like lightening!!

13. Originally Posted by esbo
I guess the fastest way would be really huge look up table, for a 32 bit int you would need
4 gigabites+ of memory though.
For a 64 bit int well, you might need a loan to buy the memory

The program might take a while to load but one loaded it would run like lightening!!
Of course, you could just use, say, a 4-bit lookup table and do 8 lookups.

14. Originally Posted by itsme86
Of course, you could just use, say, a 4-bit lookup table and do 8 lookups.
You could but it would take 8 times longer to complete (at least).

15. > You could but it would take 8 times longer to complete (at least).
Performance isn't always a problem, and this is beyond the scope of the original question.