CSAPP 第二章的一道关于位运算的题目，答案看不懂，各位帮忙想想。

[lxy42]

题目是 2.66 ，大致意思如下：

实现下面的函数：

int leftmost_one(unsigned x);

该函数返回 x 最左边的（高位） 1 的掩码，例如：x = 0xFF00 返回 0x8000，x = 0x6600 返回 0x4000。

题目要求只能使用位运算。

答案如下：

int leftmost_one(unsigned x){
    x |= (x >> 16);
    x |= (x >> 8);
    x |= (x >> 4);
    x |= (x >> 2);
    x |= (x >> 1);
    return x ^ (x >> 1);
}

我只推测出前面 5 行右移操作之后，x 变为从最左边的 1 到最右边全为 1 的形式（例如：0x6600 -> 0x7FFF ）。

提供另外一道题目 2.65 给大家看看，比这题要简单一点，题目大意：
实现`int odd_ones(unsigned x)`函数，如果 x 的 bits 中包含奇数个 1 返回 1，否则返回 0。要求只使用位运算（移位和与或非等操作）。

[bumz]

然后举个例子你就明白了，比如 00001111 ^ 00000111 = 00001000

[qysz]

我对照函数得理解：
1. 想要求得掩码，需要得到掩码位左边全为零，右边全为一得状态，再最后异或一次就得到结果；
2. 考虑掩码左边，每次或操作后都能保证仍旧为零；
3.考虑掩码右边，最极端情况下就是只有掩码为 1，剩下得全为零，在这种情况下，折半位移并进行或运算了 5 次，最
多填充了 2 的 5 次方(32)个位置的 1 （而且是不重复的） ，也就是 5 次运算保证了掩码右边全为 1 ；

[punderson]

我对答案的理解：
从最后一行看起，它使得 x 最左边的 1 的右边全是 1 了。这样的话 0x01100110 成为 0x01111111。前面 5 次异或的运算，可以这样看，把最左边的一个 1，经过右移动 n 位得到右边的 1，而 n 可以由 1,2,4,8,16 组成。所以右边任意的 n 位都可以变成 1 了。

[lxy42]

认真手写推导了一遍，有点理解了前面 5 次右移的原理了。

[bumz]

原来题主问的前 5 步。。。

一个证明的框架：

要证明
前 5 步将 00001xxx 形式变为 00001111 形式
只需证明
前 5 步将 00001000 形式变为 00001111 形式

这种情况只需模拟一遍就得到答案了
所以也就证明了前 5 步将 00001xxx 形式变为 00001111 形式

证毕（细节自行补充）