转自：/?p=253
编程之美2.1节中的扩展题第1题：如果变量是32位的Dword，则如何统计该二进制数中1的个数。
对于该题，原本的想法还是想采用书中解法三，也就是用统计1中个数的算法v&(v-1)，该算法时间复杂度为该32二进制数中“1”的个数。后来，参见了书中链接里的解法，该解法甚妙，复杂度只有若干个位运算，与“1”的数目无关。由于下面这段程序写的比较难懂，所以在这里解释一下他的解法。
解法一：
view plaincopy to clipboardprint? intCount(unsignedx) { x=x-((x>>1)&0x55555555);//1 x=(x&0x33333333)+((x>>2)&0x33333333);//2 x=(x+(x>>4))&0x0F0F0F0F;//3 x=x+(x>>8);//4 x=x+(x>>16);//5 returnx&0x0000003F;//6 }我们以0000 0000 0000 0000 0000 0000 1011 0101为例：
第一行中，x>>1是右移一位，(x>>1) 为 0000 0000 0000 0000 0000 0000 0101 1010，该结果与0101 0101 0101 0101 0101 0101 0101 0101相与，等于 0000 0000 0000 0000 0000 0000 0101 0000，实际上，((x >> 1) & 0×55555555) 该步是想得到原数据x的偶数位的数据。（代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移）然后，x-((x >> 1) & 0×55555555) 则是 用原数据减去原数据的偶数位。结果是 0000 0000 0000 0000 0000 0000 0110 0101，其实，之所有要相减就是为了得到第一位与第二位1的个数的和，第三位与第四位1的个数的和，第五位与第六位1的个数的和，以此类推。那么，为什么要用相减的方法来得到相邻两位的和呢？原理是：相邻两位1的个数的和是：A-A/2 。原数据是A，右移相当于除2。比如，如果原数据是1（01），那么一半就是0，相减后就是1，所以有1个“1”。如果原数据是3（11），那么一半就是1，相减后就是2，所有总共有2个“1”。这样，经过第一行的运算，我们得到每两个相邻位的“1”的总和。
第二行，类似的，是求将原数据第一位第二位的“1“的个数的和 与 第三位第四位的“1”的个数的和 相加。这样，第二行执行后，我们可以得到每四位的“1”的个数的和
第三行，可以得到每八位的“1”的个数的和
第四行，可以得到每16位“1”的个数的和
第五行，可以得到32位数中所有1的个数的和。
第六行，由于32位的数据，1的个数最大也就32个，不可能超过2的6位方，所以只要取最后6位数据就是所有数据1的个数的和了。
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。
解法二：
view plaincopy to clipboardprint? intCount(unsignedx) { unsignedn; n=(x>>1)&033333333333;//1 x=x-n;//2 n=(n>>1)&033333333333;//3 x=x-n;//4 x=(x+(x>>3))&030707070707;//5 x=modu(x,63);//6 returnx;//7 }这个解法更妙。需要注意的是，033333333333和033333333333都是指 八进制的数。第一行第二行连起来看，这与解法一很类似，目的是为了得到第一位与第二位的“1”的个数和。注意，第31、32位中1的个数和在这一步中被统计好了。
第一行和第三行、第四行连起来看，目的是为了得到第一位与第三位的“1”的个数的和。然后，再与上步的结果加起来，就得到第一位、第二位、第三位的“1”的个数的和。所以，从第一行到第四行就是为了得到 每三位一组的“1”的个数的和。原理是：
相邻三位的结果是：A-A/2-A/4. 算法中有两次向移。比如，第一位第二位第三位是011, 则第一次移位后为01，相减后为10，再移位后为0，相减还是10，所以有2个“1”。再比如，第一位第二位第三位是101，则第一次移位后为10，相减后为011，再移位后为1，相减后是010，所以有2个“1”。第五行是求相邻六位的1的个数第六行，比较难懂。在第五行执行完后，我们得到了七组数据，第32、31位为一组，第30-25为一组，……第6-第1为一组。所以可以写成:x_0 + x_1 * 64 + x_2 * 64 * 64 + x_3 * 64 * 64* 64+ x_4 * 64 * 64* 64* 64+ x_5 * 64 * 64* 64* 64* 64+ x_6 * 64 * 64* 64* 64* 64* 64，这个数除以63的余数 肯定 与 x_0 +……+x_6 相等（因为32位的数据最多也就32个1）简短解释：首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。
这个程序只需要十条左右指令，而且不访存，速度很快。
