Velocity Reviews > How to count bits in a unsigned int?

# How to count bits in a unsigned int?

Mockey Chen
Guest
Posts: n/a

 11-13-2005
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: http://www.velocityreviews.com/forums/(E-Mail Removed)

mensanator@aol.com
Guest
Posts: n/a

 11-13-2005

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: (E-Mail Removed)

Keith Thompson
Guest
Posts: n/a

 11-13-2005
"Mockey Chen" <(E-Mail Removed)> 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) (E-Mail Removed) <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
Guest
Posts: n/a

 11-13-2005
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
Guest
Posts: n/a

 11-13-2005
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" <(E-Mail Removed)> wrote:(E-Mail Removed)...
> "Mockey Chen" <(E-Mail Removed)> 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) (E-Mail Removed)
> <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
Guest
Posts: n/a

 11-13-2005
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
Guest
Posts: n/a

 11-13-2005
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:

> "Mockey Chen" <(E-Mail Removed)> 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 << ) != 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 << 1) != 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 << 2) != 0) +
((x & (1u << 29)) != 0) +
((x & (1u << 30)) != 0) +
((x & (1u << 31)) != 0);
}

No loop!

Jordan Abel
Guest
Posts: n/a

 11-13-2005
On 2005-11-13, Mockey Chen <(E-Mail Removed)> 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
Guest
Posts: n/a

 11-14-2005
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" <(E-Mail Removed)> wrote:(E-Mail Removed)...
> 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
Guest
Posts: n/a

 11-14-2005
On Sun, 13 Nov 2005 12:09:07 +0800, "Mockey Chen"
<(E-Mail Removed)> 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. ]