这是一道在《编程之美》上看的题目，这道题目也曾经被多家公司作为面试题，非常有趣，认真做这道题会得到很多的收获，所以整理一下这道题的解法，做个备忘。

题目的要求很简单：对于一个字节（8bit）的变量，求其二进制表示中“1”的个数，要求算法的执行效率尽可能的高。

方法一：

涉及二进制数的直接处理，并且要求执行效率，应该很容易想到位运算，于是第一种方法浮现出来，思路是将这个数的每一位与“1”做与

运算，根据1&1 = 1，1&0 = 0的规则，很容易得出结果，代码如下：

 

int binCount ( unsigned int v )
{
int count = 0;
while(v)              /*直到v为0 循环结束*/
{
  count += v&0x01;
  v>>1;              /*v向右移一位，为下一次与运算做准备*/
}
return count;
}

方法二：
方法二提供了一个效率更高的算法，但是这个方法就不容易想到，当然如果对数字敏感，也许能想到，反正我是没想到。上代码看看：

int binCount ( usigned int v )
{ int count = 0;
while ( v )
{ ++count;
i&= (i-1);/*这是重点！*/
 }
return count;
 }

方法三：
方法三提供的方法是查表法，速度也很快，具体做法就是将所有的情况都列在一个表里，直接查表的速度很快，其实这是典型的空间换时间的方法，详细代码如下：

查表法，因为只有数据8bit，直接建一张表，包含各个数中1的个数，然后查表就行。复杂度O(1)。    int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 };   
        
     int Count(int v)
     {   
        return countTable[v];   
     }

当然这些方法只是一个思路，还有很多的其他方法，这里就不说了。在wiki上还有好多高效率的算法，就是不容易懂。