Re: new module 'popcount'

[Eric Blake]

-----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             address@hidden
-----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-----