-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
According to Ben Pfaff on 7/22/2007 6:22 PM:
> +#define POPCOUNT_CALCULATION(NAME) \
> + int pop; \
> + for (pop = 0; x != 0; pop++) \
> + x &= x - 1; \
> + return pop;
You know, an O(log n) solution with no branches beats an O(n) loop any
day. In the example below, I'm assuming sizeof(unsigned int)*CHAR_BIT ==
32, but this can be generalized to other sizes:
int
popcount (unsigned int x)
{
x = ((x & 0xaaaaaaaa) >> 1) + (x & 0x55555555);
x = ((x & 0xcccccccc) >> 2) + (x & 0x33333333);
x = ((x & 0xf0f0f0f0) >> 4) + (x & 0x0f0f0f0f);
x = ((x & 0xff00ff00) >> 8) + (x & 0x00ff00ff);
return (x >> 16) + (x & 0xff);
}
- --
Don't work too hard, make some time for fun as well!
Eric Blake [EMAIL PROTECTED]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.5 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org
iD8DBQFGpAW184KuGfSFAYARAsTDAJ433J25LKKUq5E2VgHvzRmWCP1QMgCdHawU
zt2i9AkRgtF2Rnu+twAnPMs=
=Ea+C
-----END PGP SIGNATURE-----
