{* *}
code teams

Bit Count



/*
 * Counts the number of bits set. Is twice as fast as 
 * obvious shift and test method
 */
int bit_count(long x)
{
    int n = 0;

    if (x)
    {
        do 
        {
            n++;
        } while ((x &= x-1));
    }

    return(n);
}

/*
 * fast bit counter for 32 bit integers
 */
int bit_count32 (unsigned int w)
{
   w = (0x55555555 & w) + (0x55555555 & (w>> 1));
   w = (0x33333333 & w) + (0x33333333 & (w>> 2));
   w = (0x0f0f0f0f & w) + (0x0f0f0f0f & (w>> 4));
   w = (0x00ff00ff & w) + (0x00ff00ff & (w>> 8));
   w = (0x0000ffff & w) + (0x0000ffff & (w>>16));
   return w;
}

/*
 * even faster bit counter for 32 bit integers
 */
int bit_count32 (unsigned int w)
{
const unsigned int all1   = ~0;
    const unsigned int mask1h = all1 /  3  << 1;
    const unsigned int mask2l = all1 /  5;
    const unsigned int mask4l = all1 / 17;
    w -= (mask1h & w) >> 1;
    w = (w & mask2l) + ((w>>2) & mask2l);
    w = w + (w >> 4) & mask4l;
    w += w >> 8;
    w += w >> 16;
    return w & 0xff;
}