编程之美之二进制数中1的个数

问题：

对于一个字节（8bit）的变量，求其二进制中1的个数，要求算法的执行效率尽可能的高。

例如把9表示成二进制是1001，有2位是1，因此如果输入9，1的个数为2。

解法一：

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

以10100010为例：

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

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

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

[cpp] view
plaincopy

1. int Count(int a)  
2. {  
3.     int count = 0;  
4.     while(a)  
5.     {  
6.          if(a % 2 == 1)  
7.          {  
8.               count++;    
9.          }  
10.          a = a / 2;  
11.     }  
12.     return count;  
13. }  

解法二：位操作

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

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

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

[cpp] view
plaincopy

1. int Count(int a)  
2. {  
3.     int count = 0;  
4.     while(a)  
5.     {  
6.          count += a & 0x01;  
7.          a >>= 1;  
8.     }  
9.     return count;  
10. }  

位操作要比除法取余操作效率要高许多。

解法三：

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

具体解析看看原著。

[cpp] view
plaincopy

1. int Count(int a)  
2. {  
3.     int count = 0;  
4.     while(a)  
5.     {  
6.         a = a & (a-1);  
7.         count++;  
8.     }  
9.     return count;  
10. }  

解法四：分支操作

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

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

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

[cpp] view
plaincopy

1. int Count(int a)  
2. {  
3.     int count = 0;  
4.     switch(a)  
5.     {  
6.         case 0x0:  
7.              count = 0;  
8.              break;  
9.         case 0x1:  
10.         case 0x2:  
11.         case 0x4:  
12.         case 0x8:  
13.         case 0x10:  
14.         case 0x20:  
15.         case 0x40:  
16.         case 0x80:  
17.              count = 1;  
18.              break;  
19.         case 0x3:  
20.         case 0x6:  
21.         case 0xc:  
22.         case 0x18:  
23.         case 0x30:  
24.         case 0x60:  
25.         case 0xc0:  
26.              count = 2;  
27.              break;   
28.         //.....  
29.     }  
30.     return count;  
31. }  

解法五：查表法

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

[cpp] view
plaincopy

1. int CountTable[256] =       
2. {          
3.          0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,  
4.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
5.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
6.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
7.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
8.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
9.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
10.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
11.          1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,  
12.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
13.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
14.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
15.          2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,  
16.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
17.          3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,  
18.          4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8          
19. };  
20.   
21. int Count(int a)  
22. {  
23.     return CountTable[a];  
24. }