问题描述：

任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4。

若干解决方案：

普通法：

使用移位操作，判末位是否为1；移位的次数为32。

int BitCount(unsigned int n){    unsigned int c =0 ; // 计数器    while (n >0)    {        if((n &1) ==1) // 当前位是1            ++c ; // 计数器加1        n >>=1 ; // 移位    }    return c ;}

快速法：

这个方法我最喜欢，也常用。迭代n=n&(n-1)，消除最右边的1，计数。

int BitCount2(unsigned int n){    unsigned int c =0 ;    for (c =0; n; ++c)    {        n &= (n -1) ; // 清除最低位的1    }    return c ;}

动态表8bit：

使用查表法。制作包含8bit所有整数对应1的个数的表，然后匹配32位n，匹配4次。

int BitCount3(unsigned int n) {     // 建表    unsigned char BitsSetTable256[256] = {
   0} ;     // 初始化表     for (int i =0; i <256; i++)     {         BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2];     }     unsigned int c =0 ;     // 查表    unsigned char* p = (unsigned char*) &n ;     c = BitsSetTable256[p[0]] +         BitsSetTable256[p[1]] +         BitsSetTable256[p[2]] +         BitsSetTable256[p[3]];     return c ; }

静态表4bit：

所谓静态表，就是把动态表的制作结果直接放到代码中去。在数据量小的情况下，一般都会这么做。

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

静态表8bit：

int BitCount7(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] ;}

平行算法：

说实在的，这个我脑子一时转不过来，不过代码看起来很优雅。

int BitCount4(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 ; }

网友的解释：先将n写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

完美法：

先声明，这是原作者起的名字，我不赞同。代码里有取模运算，而取模这种操作，我能不用的时候坚决不用，性能很差。我也没看懂，下面会贴上网友的注释。（可能我真的是老了，工作上安逸久了，是坏事。）

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

网友的解释：

第一行代码的作用先说明一点，以0开头的是8进制数，以0x开头的是十六进制数，上面代码中使用了三个8进制数。将n的二进制表示写出来，然后每3bit分成一组，求出每一组中1的个数，再表示成二进制的形式。比如n = 50，其二进制表示为110010，分组后是110和010，这两组中1的个数本别是2和3。2对应010，3对应011，所以第一行代码结束后，tmp = 010011，具体是怎么实现的呢？由于每组3bit，所以这3bit对应的十进制数都能表示为2^2 * a + 2^1 * b + c的形式，也就是4a + 2b + c的形式，这里a,b,c的值为0或1，如果为0表示对应的二进制位上是0，如果为1表示对应的二进制位上是1，所以a + b + c的值也就是4a + 2b + c的二进制数中1的个数了。举个例子，十进制数6（0110）= 4 * 1 + 2 * 1 + 0，这里a = 1, b = 1, c = 0, a + b + c = 2，所以6的二进制表示中有两个1。现在的问题是，如何得到a + b + c呢？注意位运算中，右移一位相当于除2，就利用这个性质！4a + 2b + c 右移一位等于2a + b4a + 2b + c 右移量位等于a然后做减法4a + 2b + c –(2a + b) – a = a + b + c，这就是第一行代码所作的事，明白了吧。第二行代码的作用在第一行的基础上，将tmp中相邻的两组中1的个数累加，由于累加到过程中有些组被重复加了一次，所以要舍弃这些多加的部分，这就是&030707070707的作用，又由于最终结果可能大于63，所以要取模。需要注意的是，经过第一行代码后，从右侧起，每相邻的3bit只有四种可能，即000, 001, 010, 011，为啥呢？因为每3bit中1的个数最多为3。所以下面的加法中不存在进位的问题，因为3 + 3 = 6，不足8，不会产生进位。tmp + (tmp >> 3)-这句就是是相邻组相加，注意会产生重复相加的部分，比如tmp = 659 = 001 010 010 011时，tmp >> 3 = 000 001 010 010，相加得001 010 010 011000 001 010 010---------------------001 011 100 101011 + 101 = 3 + 5 = 8。注意，659只是个中间变量，这个结果不代表659这个数的二进制形式中有8个1。注意我们想要的只是第二组和最后一组（绿色部分），而第一组和第三组（红色部分）属于重复相加的部分，要消除掉，这就是&030707070707所完成的任务（每隔三位删除三位），最后为什么还要%63呢？因为上面相当于每次计算相连的6bit中1的个数，最多是111111 = 77（八进制）= 63（十进制），所以最后要对63取模。

位标志法：

我没测，不过，不看好位域的效率。

struct _byte {     unsigned a:1;     unsigned b:1;     unsigned c:1;     unsigned d:1;     unsigned e:1;     unsigned f:1;     unsigned g:1;     unsigned h:1; }; long get_bit_count( unsigned char b ) {    struct _byte *by = (struct _byte*)&b;     return (by->a+by->b+by->c+by->d+by->e+by->f+by->g+by->h); }

指令法：

使用微软提供的指令，首先要确保你的CPU支持SSE4指令，用Everest和CPU-Z可以查看是否支持。

unsigned int n =127 ;unsigned int bitCount = _mm_popcnt_u32(n) ;