学步园

题目看过不少次，写起来也不难，最近才发现还有很多我以前没有想到的优雅方案

关于这个的解法，http://wenku.baidu.com/view/81dfec47be1e650e52ea99e0.html 中还有很多，不少看不懂，下面是我看得懂而且比较喜欢的：

#include <cstdio>

unsigned int get_count_1(unsigned int x)
{
    unsigned int n = 0;

    while (0 != x)
    {
        x &= x - 1;
        n += 1;
    }

    return(n);
}

struct stu_bit
{
    unsigned char bit0 : 1; 
    unsigned char bit1 : 1; 
    unsigned char bit2 : 1; 
    unsigned char bit3 : 1; 
    unsigned char bit4 : 1; 
    unsigned char bit5 : 1; 
    unsigned char bit6 : 1; 
    unsigned char bit7 : 1; 
};

unsigned int get_count_byte(unsigned char * px)
{
    if (NULL == px)
    {
        throw "px is null";
    }

    stu_bit * psx = reinterpret_cast<stu_bit *>(px);
    return(psx->bit0 + psx->bit1 + psx->bit2 + psx->bit3 + 
           psx->bit4 + psx->bit5 + psx->bit6 + psx->bit7);
}

unsigned int get_count_2(unsigned int x)
{
    unsigned char * px = reinterpret_cast<unsigned char *>(&x);
    unsigned int n = 0;

    for (int i = 0; i < sizeof(x)/sizeof(*px); ++i)
    {
        n += get_count_byte(px + i);
    }

    return(n);
}

unsigned int get_count_3(unsigned int x)
{
    static unsigned int m1 = 0x55555555;
    static unsigned int m2 = 0x33333333;
    static unsigned int m4 = 0x0f0f0f0f;
    static unsigned int m8 = 0x00ff00ff;
    static unsigned int m16 = 0x0000ffff;

    x = (x & m1) + ((x >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    x = (x & m4) + ((x >> 4) & m4);
    x = (x & m8) + ((x >> 8) & m8);
    x = (x & m16) + ((x >> 16) & m16);

    return(x);
}

int main(int argc, char * argv[])
{
    unsigned int x = 0xffffffff;

    unsigned int count_1 = get_count_1(x);
    unsigned int count_2 = get_count_2(x);
    unsigned int count_3 = get_count_3(x);

    printf("count of %d is %d\n", x, count_1);
    printf("count of %d is %d\n", x, count_2);
    printf("count of %d is %d\n", x, count_3);

    return(0);
}

第一、第二种，我也能想到，第三种，花了我不少时间才看懂，还有更难理解的，就不贴了，有兴趣的自己去看 (下载不了~~~ 郁闷)