Re: Possible Bug in bitlib under Windows?

[Florian Weimer <fw@...>]

* Mike Pall:

>> count(set)  (number of bits at 1)
>
> Also called popcount. I know this one is ugly, but it's also rare.

XOR and POPCOUNT can be used to compute Hamming distances, which is
rather useful.

> And the sum-of-bitmasks solution is the best you can do right now,
> anyway.

This: <http://wiki.cs.pdx.edu/forge/popcount.html>
suggests that popcount_mult is rather fast:

/* Popcount using multiply.
   This is popcount_3() from
   http://en.wikipedia.org/wiki/Hamming_weight */
/* 11 ops plus 1 multiply, 4 long immediates, 11 stages */
static inline uint32_t
popcount_mult(uint32_t x)
{
    uint32_t m1 = 0x55555555;
    uint32_t m2 = 0x33333333;
    uint32_t m4 = 0x0f0f0f0f;
    uint32_t h01 = 0x01010101;
    x -= (x >> 1) & m1;   /* put count of each 2 bits into those 2 bits */
    x = (x & m2) + ((x >> 2) & m2);   /* put count of each 4 bits in */
    x = (x + (x >> 4)) & m4;  /* put count of each 8 bits in */
    return (x * h01) >> 24;  /* returns left 8 bits of x + (x<<8) + ... */
}