V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lxy42
V2EX  ›  编程

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

  •  
  •   lxy42 · 2019-03-04 17:40:18 +08:00 · 3446 次点击
    这是一个创建于 1851 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目是 2.66 ,大致意思如下:

    实现下面的函数:

    int leftmost_one(unsigned x);
    

    该函数返回 x 最左边的(高位) 1 的掩码,例如:x = 0xFF00 返回 0x8000x = 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。要求只使用位运算(移位和与或非等操作)。
    5 条回复    2019-03-05 13:04:59 +08:00
    bumz
        1
    bumz  
       2019-03-04 19:48:19 +08:00   ❤️ 1
    然后举个例子你就明白了,比如 00001111 ^ 00000111 = 00001000
    qysz
        2
    qysz  
       2019-03-04 20:29:49 +08:00   ❤️ 1
    我对照函数得理解:
    1. 想要求得掩码,需要得到掩码位左边全为零,右边全为一得状态,再最后异或一次就得到结果;
    2. 考虑掩码左边,每次或操作后都能保证仍旧为零;
    3.考虑掩码右边,最极端情况下就是只有掩码为 1,剩下得全为零,在这种情况下,折半位移并进行或运算了 5 次,最
    多填充了 2 的 5 次方(32)个位置的 1 (而且是不重复的) ,也就是 5 次运算保证了掩码右边全为 1 ;
    punderson
        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 了。
    lxy42
        4
    lxy42  
    OP
       2019-03-05 11:04:26 +08:00
    认真手写推导了一遍,有点理解了前面 5 次右移的原理了。
    bumz
        5
    bumz  
       2019-03-05 13:04:59 +08:00
    原来题主问的前 5 步。。。

    一个证明的框架:

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

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

    证毕(细节自行补充)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3323 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 11:25 · PVG 19:25 · LAX 04:25 · JFK 07:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.