解法一：

可以举一个8位二进制的例子。对于二进制操纵，我们除以一个2，原来数字就会减少一个0（向右移一位）。如果除的过程中有余，那么久表示当前位置有一个1。

以10100010为例：

第一次除以2时，商为1010001，余为0

第二次除以2时，商为101000，余为1

因此，考虑利用整形数据除法的特点，通过相除和判断余数的值进行分析。

int Count(int a){int count = 0;while(a){if(a % 2 == 1){count++; }a = a / 2;}return count;}

解法二：位操作

使用位操作同样达到相除的目的。

使用与操作（&）来判断最后一位是不是1，判断完后向右移一位，继续判断。

可以把这个八位数与00000001进行与操作，如果结果为1则表示这个八位数最后一位为1，否则为0

int Count(int a){int count = 0;while(a){count += a & 0x01;a >>= 1;}return count;}

解法三：

作者用到一个巧妙的方法，自己与自己减1相与，（例：10100010 & 10100001 = 10100000）从而到达消去最后一位1，通过统计循环次数达到计算1的个数的目的，这个方法减少了一定的循环次数。

具体解析看看原著。

int Count(int a){int count = 0;while(a){a = a & (a-1);count++;}return count;}

解法四：分支操作

解法三的复杂度降到O(M). 其中M为1的个数。这效率已经足够高了。

如果还不满足，还有一种方法。既然才是一个8位的数据（0~255），可以直接0~255的情况罗列出来，使用分支操作，得到答案。

这个方法看似很直接，但是效率可能会比其他方法要低。具体情况具体分析。如果a = 0比较一次就会得到答案，但是a = 255比较255次才得到答案

int Count(int a){int count = 0;switch(a){case 0x0:count = 0;break;case 0x1:case 0x2:case 0x4:case 0x8:case 0x10:case 0x20:case 0x40:case 0x80:count = 1;break;case 0x3:case 0x6:case 0xc:case 0x18:case 0x30:case 0x60:case 0xc0:count = 2;break; //.....}return count;}

解法五：查表法

直接把0~255相应1的个数直接存在数组中，采取以空间换取时间。时间复杂度为1。

int CountTable[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 };int Count(int a){return CountTable[a];}

动态建表

由于表示在程序运行时动态创建的，所以速度上肯定会慢一些，把这个版本放在这里，有两个原因

1. 介绍填表的方法，因为这个方法的确很巧妙。

2. 类型转换，这里不能使用传统的强制转换，而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。

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 ; }

先说一下填表的原理，根据奇偶性来分析，对于任意一个正整数n

1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。

2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。

再说一下查表的原理

对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。

注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以87654321（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。

10000111011001010100001100100001= 4 + 4 + 3 + 2 = 13

静态表-8bit

首先构造一个包含256个元素的表table，table[i]即i中1的个数，这里的i是[0-255]之间任意一个值。然后对于任意一个32bit无符号整数n，我们将其拆分成四个8bit，然后分别求出每个8bit中1的个数，再累加求和即可，这里用移位的方法，每次右移8位，并与0xff相与，取得最低位的8bit，累加后继续移位，如此往复，直到n为0。所以对于任意一个32位整数，需要查表4次。以十进制数2882400018为例，其对应的二进制数为10101011110011011110111100010010，对应的四次查表过程如下：红色表示当前8bit，绿色表示右移后高位补零。

第一次（n & 0xff）10101011110011011110111100010010

第二次（(n >> 8) & 0xff）00000000101010111100110111101111

第三次（(n >> 16) & 0xff）00000000000000001010101111001101

第四次（(n >> 24) & 0xff）00000000000000000000000010101011

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] ;}

5.平行算法

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写成二进制形式，然后相邻位相加，重复这个过程，直到只剩下一位。

以217（11011001）为例，有图有真相，下面的图足以说明一切了。217的二进制表示中有5个1