晚上回家，收到QQ上河马兄的留言：“计算出一个32位int数中二进制1的个数，不要用逐位比较”(是我们公司的面试题)，综合网上的解法如下：
1）内存换速度
char one[256]={0,1,1,2,1,2,……} // 此为 0-255 每个数中 1 的个数
int func(int n){
for(int i=0;n>0;n>>=8)
i+=one[n&255];
return i;
}
2）&优化
int func(int n){
int count=0;
while(n>0){
n&=(n-1);
count++;
}
return count;
}
3）最寒的算法，不看注释，还真没看懂
int func(int n)
{
unsigned int const w = n - ((n >> 1) & 0x55555555);
unsigned int const x = (w & 0x33333333) + ((w >> 2) & 0x33333333);
return (((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24);
}
第一行把n按照2比特分组划分成16组,计算各组中值为1的比特数目;
第二行把n按照4比特分组划分成8组,计算各组中值为1的比特数目;
第三行把n按照8比特分组划分成4组,计算各组中值为1的比特数目，将各组的数累加到高八位上
这里有个总结，很详细：