# How to count bits in a unsigned int?

Discussion in 'C Programming' started by Mockey Chen, Nov 13, 2005.

1. ### Mockey ChenGuest

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?

--
Regards.
Mockey Chen
Email:

Mockey Chen, Nov 13, 2005

2. ### Guest

Mockey Chen wrote:
> 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.

>
>
> --
> Regards.
> Mockey Chen
> Email:

, Nov 13, 2005

3. ### Keith ThompsonGuest

"Mockey Chen" <> writes:
> 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

--
Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

Keith Thompson, Nov 13, 2005
4. ### Guest

Mockey Chen wrote:
> 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.

--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/

, Nov 13, 2005
5. ### Mockey ChenGuest

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.

"Keith Thompson" <> wrote:...
> "Mockey Chen" <> writes:
>> 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
>
> --
> Keith Thompson (The_Other_Keith)
> <http://www.ghoti.net/~kst>
> San Diego Supercomputer Center <*>
> <http://users.sdsc.edu/~kst>
> We must do something. This is something. Therefore, we must do this.

Mockey Chen, Nov 13, 2005
6. ### peteGuest

pete, Nov 13, 2005
7. ### Christian BauGuest

In article <>,
Keith Thompson <> wrote:

> "Mockey Chen" <> writes:
> > 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

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!

Christian Bau, Nov 13, 2005
8. ### Jordan AbelGuest

On 2005-11-13, Mockey Chen <> wrote:
> 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?
>

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

Jordan Abel, Nov 13, 2005
9. ### Mockey ChenGuest

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

"pete" <> wrote:...
> Mockey Chen wrote:
>>
>> 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-db.stanford.edu/~manku/bitcount/bitcount.html
>
> --
> pete

Mockey Chen, Nov 14, 2005
10. ### Roberto WaltmanGuest

On Sun, 13 Nov 2005 12:09:07 +0800, "Mockey Chen"
<> wrote:

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

[ return address is invalid. ]

Roberto Waltman, Nov 14, 2005
11. ### Flash GordonGuest

Mockey Chen wrote:
> 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" <> wrote:...

<snip>
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.

Flash Gordon, Nov 14, 2005
12. ### Emmanuel DelahayeGuest

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.

--
A+

Emmanuel Delahaye

Emmanuel Delahaye, Nov 14, 2005