编程之美2.1节中的扩展题第1题：如果变量是32位的Dword，则如何统计该二进制数中1的个数。
对于该题，我原本的想法还是想采用书中解法三，也就是用统计1中个数的算法v&(v-1)，该算法时间复杂度为该32二进制数中“1”的个数。
后来，我参见了[1]中的解法，该解法甚妙，复杂度只有若干个位运算，与“1”的数目无关。由于[1]写的比较难懂，所以在这里解释一下他的解法。
解法一：
int Count(unsigned x)
{
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
return x & 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) & 0x55555555) 该步是想得到原数据x的偶数位的数据。（代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移） 然后，x-((x >> 1) & 0x55555555) 则是 用原数据减去原数据的偶数位。结果是 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的个数的和了。
这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。[1].
解法二：
int Count(unsigned x)
{
unsigned n;
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
return x; //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的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。
这个程序只需要十条左右指令，而且不访存，速度很快。