0/1的奥秘:直接取二进制中1的个数的算法

【问题描述】：给一段位数为n的二进制数，统计其中1的个数

【算法概述】：将二进制数按照每2位分组，计算每2位中1的个数，保存在一个二进制数中。然后迭代上述过程，就得到了每4位中1的个数，每8位中的 1的个数，迭代下去，最终得到n位中1的个数

【算法复杂度】：log以2为底的n

【算法描述】：摘自http://www.loveunix.net/html/200405/29967.html ， 作者: wingc  发布日期: 2004-5-21

unsigned long CountBit(unsigned long X)

{

X = (X & 0x55555555) + (X >> 1 & 0x55555555);

X = (X & 0x33333333) + (X >> 2 & 0x33333333);

X = (X & 0x0F0F0F0F) + (X >> 4 & 0x0F0F0F0F);

X = (X & 0x00FF00FF) + (X >> 8 & 0x00FF00FF);

X = (X & 0x0000FFFF) + (X >> 16 & 0x0000FFFF);

return(X);

}
/*
0x55555555: 01010101010101010101010101010101
0x33333333: 00110011001100110011001100110011
0x0F0F0F0F: 00001111000011110000111100001111
0x00FF00FF: 00000000111111110000000011111111
0x0000FFFF: 00000000000000001111111111111111
*/

作者: wingc  发布日期: 2004-5-22

哈哈，经指点，大概懂了，其实偶一直在想那个十进制数的变换过程应该有数学公式推导，导致偶一直在十进制数上打转，要是把注意力仍停留在二进制数 上，就不难理解了。（有可能真的有数学公式吧，但是与其找15->10->4的公式，不如直接观察二进制串的变化过程更容易明白）

偶 再拿一个长点的数（8位）说明一下，无双大哥看看偶真的理解没有

<!-- emo&<img src="http://bbs.loveunix.net/images/smilies/smile.gif" align="absmiddle" border="0">--><!-- endemo-->

10101100（172）
| 第一次迭代(与01010101运算)
V
00000100 + 01010100 = 01 01 10 00

这一步将10101100每 两位上1的个数1(01)、1(01)、2(10)、0(00)计算出来了，但是这个值由于“权值”的问题，就是二进制数所在位数的问题，除了最后两位 00外前面三个都不能表达出真实意义，所以还需迭代

01011000
| 第二次迭代（与00110011运算）
V
00010000 + 00010010 = 0010 0010
这一步将10101100每四位数上1的个数2(0010)、2（0010）计算出来了，其实就是将上一步 运算两种颜色的值分别成对相加得到，同时，调整调整了“权值”，上一步中第一个01和第三个10的“权值”都下降两位，这样使后四位的0010的“权值” 已经“正常”，可以表达实际2的意义了，但前四位仍在高位，还不能真实表达，仍需迭代

00100010
| 第三次迭代（与00001111运算）
V
0010 + 0010 = 0100(4)
这一步得到了1的个数的实际意义值，上一步 第一个0010由于“权值”问题，还不能真实表达，而这一次，第一个0010“权值”下降四位，可以表达实际意义了，这样加起来就是实际的1的个数了

总 结，其实就是先算出每两位1的个数的值，但是由于所在二进制位数的问题，导致了除最后两位的值有真实的1的计数意义外，其他的都还不能真实表达，所以来第 二次迭代，这次迭代计算出了每四位的1的个数，但是同样的原因，出了最后四位值有真实的计数意义外，前四位仍然不能真实表达，再来第三次迭代，这次迭代算 出了每八位的1的个数，也就是这个8位二进制数的1的个数啦~~