给定一个32位无符号整数n，求n的二进制表示中1的个数

bc_count.c

/* 
 * 给定一个32位无符号整数n，求n的二进制表示中1的个数
 * 算法来自 http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html
 */

#include <stdio.h>

#define PRT(func, num) (printf("%s(%x):\t%d\n", #func, num, func(num)))

unsigned int bc_plain(unsigned int n)
{
    unsigned int count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

unsigned int bc_quick(unsigned int n)
{
    unsigned int count = 0;
    for (; n; ++count) {
        n &= (n - 1);
    }
    return count;
}

unsigned int bc_dtable(unsigned int n)
{
    unsigned char table[256] = {0};
    unsigned int i;
    unsigned char *p = (unsigned char *)&n;

    for (i = 0; i < 256; ++i) {
        table[i] = (i & 1) + table[i / 2];
    }
    return table[p[0]] + table[p[1]] + table[p[2]] + table[p[3]];
}

unsigned int bc_stable4(unsigned int n)
{
    unsigned int count = 0;
    unsigned int table[16] = {
        0, 1, 1, 2,
        1, 2, 2, 3,
        1, 2, 2, 3,
        2, 3, 3, 4,
    };
    while (n) {
        count += table[n & 0xf];
        n >>= 4;
    }
    return count;
}

unsigned int bc_stable8(unsigned int n)
{
    unsigned int table[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,        
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,       
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,        
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,        
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    };

    return table[n & 0xff] + table[(n >> 8) & 0xff] +
           table[(n >> 16) & 0xff] + table[(n >> 24) & 0xff];
}

unsigned int bc_parallel(unsigned int n)
{
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    return n;
}

unsigned int bc_perfect(unsigned int n)
{
    unsigned int tmp = n - ((n >> 1) & 033333333333) - ((n >> 2) & 011111111111);
    return ((tmp + (tmp >> 3)) & 030707070707) % 63;
}

void test_prt(unsigned int num)
{
    PRT(bc_plain, num);
    PRT(bc_quick, num);
    PRT(bc_dtable, num);
    PRT(bc_stable4, num);
    PRT(bc_stable8, num);
    PRT(bc_parallel, num);
    PRT(bc_perfect, num);
    puts("");
}

int main()
{
    unsigned int tn[] = {
        0x12345678,
        0x11111111,
        0xFFFFFFFF,
        0x002FAE32
    };
    int sz = sizeof(tn) / sizeof(*tn);
    int i;
    for (i = 0; i < sz; ++i) {
        test_prt(tn[i]);
    }
    return 0;
}