CS:APP 家庭作业 2.65 题：
写出代码实现如下函数：
这道题左边有四颗星，实际的难度也确实很高。在苦思冥想没有结果之后，我在github上找到了答案。令人备受打击的是答案一时也没有看懂，在纸上推导之后才明白答案为何是正确的。如果让我来做，断然是想不到这种巧妙的方法。
这道题目是要判断一个32位整数的位模式中是否含有偶数个1，需要做的就是在该整数确实有偶数个1时返回1，否则返回0。由于偶数个1的位模式有太多种形式，必然无法用掩码的方式提取出这种特征。由于我确实没有更好的思路，下面直接看别人的解答：
1 2 3 4 5 6 7 8 9 10 int odd_ones (unsigned x) { x ^= x >> 16 ; x ^= x >> 8 ; x ^= x >> 4 ; x ^= x >> 2 ; x ^= x >> 1 ; x &= 0x1 ; return !x; }
这个答案一眼看上去就给人极大的启发，在这种极大启发带来的欣喜下我以为可以看出这种做法的合理性，最后还是得推导每一步才明白。
题目是关于32位整数的，为了推导时的方便，不妨以8位为例：
1 2 3 4 5 6 7 8 int odd_ones (uint8_t x) { x ^= x >> 4 ; x ^= x >> 2 ; x ^= x >> 1 ; x &= 0x1 ; return !x; }
输入8位整数x的位模式可以写作：x 0 = [ x 7 , x 6 , x 5 , x 4 , x 3 , x 2 , x 1 , x 0 ] x^0 = [x_7, x_6, x_5, x_4, x_3, x_2, x_1, x_0] x 0 = [ x 7 , x 6 , x 5 , x 4 , x 3 , x 2 , x 1 , x 0 ] x ^= x >> 4即是：
[ x 7 , x 6 , x 5 , x 4 , x 3 , x 2 , x 1 , x 0 ] ∧ [ 0 , 0 , 0 , 0 , x 7 , x 6 , x 5 , x 4 ] \begin{aligned}
[&x_7, &x_6, &x_5, &x_4, &x_3, &x_2, &x_1, &x_0&] \wedge \\
[&0, &0, &0, &0, &x_7, &x_6, &x_5, &x_4&]
\end{aligned} [ [ x 7 , 0 , x 6 , 0 , x 5 , 0 , x 4 , 0 , x 3 , x 7 , x 2 , x 6 , x 1 , x 5 , x 0 x 4 ] ∧ ]
这个运算的结果可以简述如下：x的高四位保持不变，第四位变为原x的第四位和高四位按位异或。这个结果又可以详细描述如下：
x 1 = [ x 7 , x 6 , x 5 , x 4 , x 3 ∧ x 7 , x 2 ∧ x 6 , x 1 ∧ x 5 , x 0 ∧ x 4 ] x^1 = [x_7, x_6, x_5, x_4, x_3 \wedge x_7, x_2 \wedge x_6, x_1 \wedge x_5, x_0 \wedge x_4]
x 1 = [ x 7 , x 6 , x 5 , x 4 , x 3 ∧ x 7 , x 2 ∧ x 6 , x 1 ∧ x 5 , x 0 ∧ x 4 ]
如此种过程向下推广，则第二行运算是
[ x 7 , x 6 , x 5 , x 4 , x 3 ∧ x 7 , x 2 ∧ x 6 , x 1 ∧ x 5 , x 0 ∧ x 4 ] ∧ [ 0 , 0 , x 7 , x 6 , x 5 , x 4 , x 3 ∧ x 7 , x 2 ∧ x 6 ] \begin{aligned}
[&x_7, &x_6, &x_5, &x_4, &x_3 \wedge x_7, &x_2 \wedge x_6, &x_1 \wedge x_5, &x_0 \wedge x_4&] \wedge \\
[&0, &0, &x_7, &x_6, &x_5, &x_4, &x_3 \wedge x_7, &x_2 \wedge x_6&]
\end{aligned} [ [ x 7 , 0 , x 6 , 0 , x 5 , x 7 , x 4 , x 6 , x 3 ∧ x 7 , x 5 , x 2 ∧ x 6 , x 4 , x 1 ∧ x 5 , x 3 ∧ x 7 , x 0 ∧ x 4 x 2 ∧ x 6 ] ∧ ]
这个结果是：
x 2 = [ x 7 , x 6 , x 5 ∧ x 7 , x 4 ∧ x 6 , x 3 ∧ x 5 ∧ x 7 , x 2 ∧ x 4 ∧ x 6 , x 1 ∧ x 3 ∧ x 5 ∧ x 7 , x 0 ∧ x 2 ∧ x 4 ∧ x 6 ] x^2 = [x_7, x_6, x_5 \wedge x_7, x_4 \wedge x_6, x_3 \wedge x_5 \wedge x_7, x_2 \wedge x_4 \wedge x_6, x_1 \wedge x_3 \wedge x_5 \wedge x_7, x_0 \wedge x_2 \wedge x_4 \wedge x_6]
x 2 = [ x 7 , x 6 , x 5 ∧ x 7 , x 4 ∧ x 6 , x 3 ∧ x 5 ∧ x 7 , x 2 ∧ x 4 ∧ x 6 , x 1 ∧ x 3 ∧ x 5 ∧ x 7 , x 0 ∧ x 2 ∧ x 4 ∧ x 6 ]
第三行运算是：
[ x 7 , x 6 , x 5 ∧ x 7 , x 4 ∧ x 6 , x 3 ∧ x 5 ∧ x 7 , x 2 ∧ x 4 ∧ x 6 , x 1 ∧ x 3 ∧ x 5 ∧ x 7 , x 0 ∧ x 2 ∧ x 4 ∧ x 6 ] ∧ [ 0 , x 7 , x 6 , x 5 ∧ x 7 , x 4 ∧ x 6 , x 3 ∧ x 5 ∧ x 7 , x 2 ∧ x 4 ∧ x 6 , x 1 ∧ x 3 ∧ x 5 ∧ x 7 ] \begin{aligned}
[&x_7, &x_6, &x_5 \wedge x_7, &x_4 \wedge x_6, &x_3 \wedge x_5 \wedge x_7, &x_2 \wedge x_4 \wedge x_6, &x_1 \wedge x_3 \wedge x_5 \wedge x_7, &x_0 \wedge x_2 \wedge x_4 \wedge x_6&] \wedge \\
[&0, &x_7, &x_6, &x_5 \wedge x_7, &x_4 \wedge x_6, &x_3 \wedge x_5 \wedge x_7, &x_2 \wedge x_4 \wedge x_6, &x_1 \wedge x_3 \wedge x_5 \wedge x_7&]
\end{aligned} [ [ x 7 , 0 , x 6 , x 7 , x 5 ∧ x 7 , x 6 , x 4 ∧ x 6 , x 5 ∧ x 7 , x 3 ∧ x 5 ∧ x 7 , x 4 ∧ x 6 , x 2 ∧ x 4 ∧ x 6 , x 3 ∧ x 5 ∧ x 7 , x 1 ∧ x 3 ∧ x 5 ∧ x 7 , x 2 ∧ x 4 ∧ x 6 , x 0 ∧ x 2 ∧ x 4 ∧ x 6 x 1 ∧ x 3 ∧ x 5 ∧ x 7 ] ∧ ]
对于这一步运算，但看其最低位，值为：
x 1 ∧ x 3 ∧ x 5 ∧ x 7 ∧ x 0 ∧ x 2 ∧ x 4 ∧ x 6 \begin{aligned}
&x_1 \wedge x_3 \wedge x_5 \wedge x_7 \wedge \\
&x_0 \wedge x_2 \wedge x_4 \wedge x_6
\end{aligned} x 1 ∧ x 3 ∧ x 5 ∧ x 7 ∧ x 0 ∧ x 2 ∧ x 4 ∧ x 6
可以看到，这一位的值实际上是该整数x的所有位的异或。也就是说，只要该整数的位模式有偶数个1(同时0也是偶数个)，那么该位最终的异或结果就一定是1 ^ 1 = 0，否则就一定为1 ^ 0 = 1。也就是说，当x有偶数个1时，该最低位是0，反之则为1。因此可以通过提取该最低为再取反来作为函数的返回结果。
当出现判断某值是否在一个集合中出现偶数次 或奇数次 时，应该考虑异或的使用。
当需要做到将一个集合中所有的数值做异或，且这个所有值的异或应出现在集合的起始或结尾位置时，应考虑这种逐步移位，每次减半的做法。