这是一个创建于 2109 天前的主题，其中的信息可能已经有所发展或是发生改变。
题目是 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 ）。
第 1 条附言 · 2019-03-05 11:09:31 +08:00
提供另外一道题目 2.65 给大家看看，比这题要简单一点，题目大意：
实现`int odd_ones(unsigned x)`函数，如果 x 的 bits 中包含奇数个 1 返回 1，否则返回 0。要求只使用位运算（移位和与或非等操作）。
实现`int odd_ones(unsigned x)`函数，如果 x 的 bits 中包含奇数个 1 返回 1，否则返回 0。要求只使用位运算（移位和与或非等操作）。
 |
1
bumz 2019-03-04 19:48:19 +08:00  1
然后举个例子你就明白了，比如 00001111 ^ 00000111 = 00001000
|
 |
2
qysz 2019-03-04 20:29:49 +08:00 1
我对照函数得理解：
1. 想要求得掩码，需要得到掩码位左边全为零，右边全为一得状态，再最后异或一次就得到结果； 2. 考虑掩码左边，每次或操作后都能保证仍旧为零； 3.考虑掩码右边，最极端情况下就是只有掩码为 1，剩下得全为零，在这种情况下，折半位移并进行或运算了 5 次，最 多填充了 2 的 5 次方(32)个位置的 1 （而且是不重复的） ，也就是 5 次运算保证了掩码右边全为 1 ； |
 |
3
punderson 2019-03-04 20:52:50 +08:00 1
我对答案的理解：
从最后一行看起，它使得 x 最左边的 1 的右边全是 1 了。这样的话 0x01100110 成为 0x01111111。前面 5 次异或的运算，可以这样看，把最左边的一个 1，经过右移动 n 位得到右边的 1，而 n 可以由 1,2,4,8,16 组成。所以右边任意的 n 位都可以变成 1 了。 |
 |
4
lxy42 OP 认真手写推导了一遍，有点理解了前面 5 次右移的原理了。
|
|
5
bumz 2019-03-05 13:04:59 +08:00
原来题主问的前 5 步。。。
一个证明的框架： 要证明 前 5 步将 00001xxx 形式变为 00001111 形式 只需证明 前 5 步将 00001000 形式变为 00001111 形式 这种情况只需模拟一遍就得到答案了 所以也就证明了前 5 步将 00001xxx 形式变为 00001111 形式 证毕（细节自行补充） |
Select Language