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

题目的要求很简单:对于一个字节(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上还有好多高效率的算法,就是不容易懂。