Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   How to count bits in a unsigned int? (http://www.velocityreviews.com/forums/t440134-how-to-count-bits-in-a-unsigned-int.html)

 Mockey Chen 11-13-2005 04:09 AM

How to count bits in a unsigned int?

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@gmail.com

 mensanator@aol.com 11-13-2005 04:18 AM

Re: How to count bits in a unsigned int?

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: mockey.chen@gmail.com

 Keith Thompson 11-13-2005 05:40 AM

Re: How to count bits in a unsigned int?

> 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) kst-u@mib.org <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.

 websnarf@gmail.com 11-13-2005 06:45 AM

Re: How to count bits in a unsigned int?

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/

 Mockey Chen 11-13-2005 08:40 AM

Re: How to count bits in a unsigned int?

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" <kst-u@mib.org> wrote:lny83tqf5f.fsf@nuthaus.mib.org...
>> 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) kst-u@mib.org
> <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.

 pete 11-13-2005 11:51 AM

Re: How to count bits in a unsigned int?

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/bi.../bitcount.html

--
pete

 Christian Bau 11-13-2005 12:12 PM

Re: How to count bits in a unsigned int?

In article <lny83tqf5f.fsf@nuthaus.mib.org>,
Keith Thompson <kst-u@mib.org> 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 "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!

 Jordan Abel 11-13-2005 11:58 PM

Re: How to count bits in a unsigned int?

On 2005-11-13, Mockey Chen <mockey.chen@google.com> 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

 Mockey Chen 11-14-2005 02:18 PM

Re: How to count bits in a unsigned int?

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" <pfiland@mindspring.com> wrote:437728D0.50BB@mindspring.com...
> 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/bi.../bitcount.html
>
> --
> pete

 Roberto Waltman 11-14-2005 03:28 PM

Re: How to count bits in a unsigned int?

On Sun, 13 Nov 2005 12:09:07 +0800, "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?
>

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