１であるビットの数を数える方法（C言語）

最上位２ビットには使えませんが、以下の最速バージョンはC MAGAZINE 1996年8月号に掲載されたものですが、原理を分かれば、とても感動的なものです。
ビット演算って、凄い！って感心させます。

int numofbits(int bits)
{
    int num;

    num = (bits >> 1) & 03333333333;
    num = bits - num - ((num >> 1) & 03333333333);
    num = ((num + (num >> 3)) & 0707070707) % 077;
    return num;
}

もう一つは、１の数分のループが必要です(Brian Kernighan氏)。

int numofbits(unsigned int bits)
{
    int count=(bits==0)?0:1;
    while ((x&=(x-1)) != 0)
    {
        count++;
    }
    return count;
}

ルックアップテーブルを使う方法は以下の通りです。

//ルックアップテーブル
static const unsigned char BitsSetTable256[256] =
{
    # define B2(n) n, n+1, n+1, n+2
    # define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
    # define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
        B6(0), B6(1), B6(1), B6(2)
};
//方法１
int numofbits_1(unsigned int v)
{
    return (BitsSetTable256[v & 0xff] +
        BitsSetTable256[(v >> 8) & 0xff] +
        BitsSetTable256[(v >> 16) & 0xff] +
        BitsSetTable256[v >> 24]);
}
//方法２
int numofbits_2(unsigned int v)
{
    unsigned char * p = (unsigned char *) &v;
    return (BitsSetTable256[p[0]] +
        BitsSetTable256[p[1]] +
        BitsSetTable256[p[2]] +
        BitsSetTable256[p[3]]);
}

アルゴリズムの大家であるKnuth の本には、以下のものがあります。

int numofbits(long bits) {
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

参考文献：

• http://www.st.rim.or.jp/~phinloda/cqa/cqa15.html
• Henry S. Warren Hacker's Delight