How many bits are '1' in an integer variable?

Quote:

---

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.

Quote:

---

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

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.

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.

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

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

Quote:

---

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


Quzah.

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++ )
count+= (mask& var>>i );

---

or even

Code:

---

for ( i = 0; i < sizeof(int)*8 ; i++, count+= (mask& var>>i ));

---

:D

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



Quzah.

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++ )
count+= (mask& var>>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.

You could even do this:

Code:

---

int count_ones(unsigned int var)
{
  unsigned int mask = 0x1;
  int count = 0;
  while (var != 0)
  {
      count += var & mask;
      var >>= 1;
  }
  return count;
}

---

I prefer the if so I'd do:

Code:

---

int count_ones(unsigned int var)
{
  unsigned int mask = 0x1;
  int count = 0;
  while (var != 0)
  {
      if (var & mask)
        count++;
      var >>= 1;
  }
  return count;
}

---

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:D

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

Quote:

---

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:D

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.

Quote:

---

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

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