leftmost_one

发表于 更新于 分类于 阅读次数： 本文字数： 952 阅读时长 ≈ 1 分钟

CS:APP homework 2.66 题：

写出代码实现如下函数：
/*

  • Generate mask indicating leftmost 1 in x, Assume w = 32.
  • For example, 0xFF00 -> 0x8000, and 0x6000 -> 0x4000.
  • If x = 0, return 0
    */
    int leftmost_one(unsigned x);
    函数应该遵循位级整数编码规则，不过可以假设数据类型 int 有 w=32 位。
    你的代码最多只能包含15个算术运算，位运算和逻辑运算。
    提示：先将 x 转换成形如[0…011…1]的位向量。

一开始没有注意到提示是什么意思，后来才反应过来是要将从左侧第一个1开始向右都设置为1。看了答案发现解法与2.65题偶数个1十分相似：

1
2
3
4
5
6
7
8
9
int leftmost_one(unsigned x)
{
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return (x >> 1) + (x && 0x1);
}

结合2.65题的启示，这道题的解法可能是要做到每一位的或运算。经过推导 w = 4 的情况：

x=[x3,x2,x1,x0]x = [x_3, x_2, x_1, x_0]

则最终 (x |= x >> 16) 的结果为：

x=[x0,x0∣x1,x0∣x1∣x2,x0∣x1∣x2∣x3]x = [x_0, x_0 | x_1, x_0 | x_1 | x_2, x_0 | x_1 | x_2 | x_3]

这一结果可以将从最左侧的1的位置以右的所有位都置为1，具体的情形是：这一结果的位模式从最左侧开始分别是原位向量的最左侧向右逐步取或，这样一旦原位模式中有1存在，则该位置开始向右都将变为1。

完成上述过程后，将所得的结果向右逻辑移动1位，相当于最左侧位置再向右一位开始的位都为1，此时若再加1，则由于进位，原位向量中最左侧1的位置将进位为1，而其余位置为0，这样就达到了题目要求。当 x == 0 时，x && 0x1 得到结果0，最终返回0。

关于最左侧的1的情况就是这样。