Re: HAKMEM #169

chase@centerline.com (David Chase) writes:
| int
| popcount(unsigned long n)
| {
| unsigned long x, y;
| x = n & 0x55555555;
| y = (n >> 1) & 0x55555555;
| n = x + y;
.....
| y = (n >> 8) & 0x00ff00ff;
| n = x + y;
| x = n & 0x0000ffff;
| y = (n >> 16);
| n = x + y;
| return n;
| }


Yes, this is a pretty fast version. The big constants hurt a RISC
though, so I removed the masking from bit that weren't used. This way
of counting takes 16 cycles when used in a loop on a SPARC.


Needless to say that this is even a greater win on a 64 bit
architecture. This really should be part of any C-programmers bagage,
but browsing fx. the Linux sources, we clearly see it ain't.


#ifdef __GNUC__
inline
#endif
static unsigned
bitcount(unsigned x)
{
    /* Clasical way to count set bits in a word, sligtly optimized */
    /* This takes 16 SPARC cycles, when done in a loop ;^) */
    /* Assumes a 32-bit architecture */


    x = (x >> 1 & 0x55555555) + (x & 0x55555555);
    x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
    x = ((x >> 4) + x) & 0x0f0f0f0f;
    x = ((x >> 8) + x);
    return (x + (x >> 16)) & 0xff;
}


...now back to compiler issues.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.