高效计算二进制序列1的个数

记的遇到过一道程序题：判断两个整数二进制形式中1的个数多少。很明显的方法是分别写出这两个数的二进制形式计算每个的二进制个数，进行比较，然而如何高效的计算某个整数的1的个数成为了算法设计的优劣比较。这里采用8位的二进制作为说明。

第一种方法

我们知道一个整数每次除以2就会减少一个0，因此只需对这个数对二取余数，然后依次除二即可。算法如下：

int count（int num）

{

int sum = 0;

while(num)

{

if(num%2!=0)

sum++;

num/=2;
}

return sum;
}

第二种方法

在以一种方法的引导下，我们可以想到移位运算，每次只需判断最后一位即可。如下：

Int count(int num)

{

Int sum = ;

While(num)

{

sum+=num&0x01;

Num>>=1;
}

Return sum;

}

第三那种方法

我们发现即使这样这个算法的时间复杂度为log2N,是否还可以更快呢？能不能找到一种算法的时间复杂度仅与1的个数有关。例如有01001100这个里面有三个1，怎样进行一次操作使得1的个数减少，我们知道对于01000000类型的只有一个1，有01000000&（01000000-00000001）=0，因此对于01001100而言执行一次N&（N-1）操作就会减少一个一的个数，因此我们有如下算法

Int count(int num)

{

Int sum = 0;

While(num)

{

Num&=(num-1);

Sum++;
}

Return 0;
}

意义发现此时的算法复杂度为O(M),其中M为该整数中1的个数。这个算法的复杂度已经相当高了。那么还能不能更快点？

第四种方法

既然只有8位那么我们可以列出1~256每个数中1的个数，进行打表。如下

Int count（Int num）

{

Int sum[256]={0，1，1，2，1，2……6，7，7，8};

Return(num);
}

这个复杂度为O(1)，达到了前人无法企及的高度，这是典型的空间换时间方法，然而这种方法在对算法世间性能要求严格的前提下，优势相当明显。