How to count bits in a unsigned int?

[Mockey Chen]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Thanks in advance.

 

[mensanator]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Use the GMP library:

[Function] unsigned long int mpz popcount (mpz_t op)
If op  0, return the population count of op, which is the number of 1
bits in the binary
representation. If op < 0, the number of 1s is infinite, and the return
value is MAX ULONG,
the largest possible unsigned long.

 

[Keith Thompson]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

The "please do not use loop if possible" clause makes this sound very
much like homework. If so, please give us your instructor's e-mail
address so we can submit the answer directly.

 

[websnarf]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Look for "Pop Count" in AMD's Optimization documentation. They give a
very fast algorithm.

 

[Mockey Chen]

oops, homework? I never asked anyone to help me because of homework
when I was a student.

I saw this question in another bulletin board system. they guies give some
solutions for this topic, but not perfect, so I copy the question to here.

Since there are guru in this news group, I thought I can get a more better.
Now, I got a perfect answer is homework, haha. I become a student again.

 

[pete]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

First day on the net?

http://www.google.com/search?hl=en&ie=ISO-8859-1&q=counts+bits+C+32

http://www-db.stanford.edu/~manku/bitcount/bitcount.html

 

[Christian Bau]

The "please do not use loop if possible" clause makes this sound very
much like homework. If so, please give us your instructor's e-mail
address so we can submit the answer directly.

But it is very simple (assuming thirtytwo bit unsigned int):

int bitcount (unsigned int x)
{
return
((x & (1u << 0)) != 0) +
((x & (1u << 1)) != 0) +
((x & (1u << 2)) != 0) +
((x & (1u << 3)) != 0) +
((x & (1u << 4)) != 0) +
((x & (1u << 5)) != 0) +
((x & (1u << 6)) != 0) +
((x & (1u << 7)) != 0) +
((x & (1u << 8)) != 0) +
((x & (1u << 9)) != 0) +
((x & (1u << 10)) != 0) +
((x & (1u << 11)) != 0) +
((x & (1u << 12)) != 0) +
((x & (1u << 13)) != 0) +
((x & (1u << 14)) != 0) +
((x & (1u << 15)) != 0) +
((x & (1u << 16)) != 0) +
((x & (1u << 17)) != 0) +
((x & (1u << 18)) != 0) +
((x & (1u << 19)) != 0) +
((x & (1u << 20)) != 0) +
((x & (1u << 21)) != 0) +
((x & (1u << 22)) != 0) +
((x & (1u << 23)) != 0) +
((x & (1u << 24)) != 0) +
((x & (1u << 25)) != 0) +
((x & (1u << 26)) != 0) +
((x & (1u << 27)) != 0) +
((x & (1u << 28)) != 0) +
((x & (1u << 29)) != 0) +
((x & (1u << 30)) != 0) +
((x & (1u << 31)) != 0);
}

No loop!

 

[Jordan Abel]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Thanks in advance.

Make a lookup table with 256 elements. check each 8-bit group in
turn. unsigned char weight[256] = {
0, 1, 1, 2, 1, 2, 2, 3,
}; etc

 

[Mockey Chen]

Excellent. thanks.

I find a solution in c++:

#include <bitset>
#include <iostream>
int main()
{
unsigned long x;
std::cin >> x;
std::bitset<32> bs(x);
std::cout << bs.count() << std::endl;
return 0;
}

 

[Roberto Waltman]

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Thanks in advance.

The "best way" in my book uses a loop:

unsigned int bit_count(unsigned int n)
{
unsigned int count = 0;
while (n)
{
/* clear rightmost '1' bit */
n &= (n-1);
count++;
}
return count;
}

Ref: "Hacker's Delight"

Roberto Waltman

[ Please reply to the group, ]
[ return address is invalid. ]

 

[Flash Gordon]

Excellent. thanks.

I find a solution in c++:

<snip>

1) Please don't top post. You reply belongs under the text you are
replying to (after suitable trimming), not above. See most of the
posts on this group for examples.

2) We don't care about C++ solutions here, this is comp.lang.c. If you
want C++ go to comp.lang.c++

"pete" <[email protected]> wrote:[email protected]...

<snip>

 

[Emmanuel Delahaye]

Mockey Chen a écrit :

On 32-bit platform, give you a unsigned int?
what is the best way to get how many bits equal to 1.
please do not use loop if possible?

Use recursion.