csapp 笔记(1) data lab

最近跌跌撞撞的完成了 csapp datalab, 记录一下 bit operations 一些基本技巧.

只用非和与实现异或 `x^y`.

合法操作符: ~, &. 最大步数: 14.

利用真值表容易得到 x^y = ~x & y + x & ~y. 然后可以用德摩根定律 ~(x + y) = ~x & ~y 把 + 转成 & 和 ~.

int bitXor(int x, int y) {
  return ~(~(~x & y) & ~(x & ~y));
}

判断 x 是否是补码的最大正数.

合法操作符: ! ~ & ^ | +, 最大步数: 10.

因为不准用移位, 所以只能利用 Tmax(0x7FFFFFFF) 的性质. Tmax + 1 和 ~Tmax 相等, 还需要排除掉 -1(0xFFFFFFFF), 即

int isTmax(int x) {
  return !((x+1) ^ (~x)) & !!(~x);
}

不过这里 x+1 可能会溢出, 而有符号整数的溢出是 undefined behavior. 没想到好的办法解决.

判断 x 是否所有奇数位上的数字都为1. (最低位为0位, 最高位为31位).

合法操作符: ! ~ & ^ | + « », 最大操作数: 12.

示例: allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1

只要确保奇数位上为1(偶数位不管), 那么利用0xAAAAAAAA做掩码就好. !(~x & 0xAAAAAAAA). 由于要求常数不得大于 0xFF, 所以需要用0xAA移位2次来得到0xAAAAAAAA.

求 -x.

合法操作符: ! ~ & ^ | + « », 最大步数: 5.

补码的特性, -x = ~x + 1. 我觉得很神奇也很重要.

判断 x 是否是 ASCII 字符 ‘0’ 到 ‘9’, 即 0x30 <= x <= 0x39.

合法操作符: ! ~ & ^ | + « », 最大步数: 15.

0x30 到 0x39 的前28位都是 0x3, 后4位小于 10.

int isAsciiDigit(int x) {
  // last 4 bit < 10
  int last4 = x & 0xF + (~0xA + 1);
  // first 28 bit must be 0x3
  int first28 = (x >> 4) ^ 0x3;
  return !first28 & (last4 >> 31);
}

实现条件判断 x ? y : z.

合法操作符: ! ~ & ^ | + « », 最大步数: 16.

这个也蛮重要的. x = 0 时很容易想到 x & y | ~x & z, 所以只要在 x != 0 时让它等于 0xFFFFFFFF 就好了.

int conditional(int x, int y, int z) {
  int bit = !x;
  int mask = (bit << 31) >> 31;
  return (~mask & y) | (mask & z);
}

实现小于等于, 即如果 `x <= y`. 则返回1, 否则返回 0.

合法操作符: ! ~ & ^ | + « », 最大步数: 24.

容易想到利用异或 diff = x ^ y 来查看两个数的差别. x 的符号位必然是 1, 才会有 x < y. 如果符号位相同的话, 异或值中第一个1出现位置必然和 y 相同, 才能得到 x < y.

然后可以利用一个技巧. 和 0 异或会保持不变, 和 1 异或相当于取非. 可以根据这个取一些常数作为掩码, 从而可以设置操作数中的特定位.

比如x ^ 0x7FFFFFFF, 可以让 x 的符号位不变, 而其他位取非, 再利用 diff 中第一个 1 的位取与, 就可以判断是否有 x < y, 然后在利用 !diff 判断是否 x == y.

另一种思路是先得到 x > y 再取非, 这样就是通过 (x ^ 0x80000000) 将符号位取非, 其余位不变, 原理是一样的.

diff 也有个技巧, 将除了从最高位到最低位第一个出现的1之外的所有位置为

见代码.

int isLessOrEqual(int x, int y) {
  // mask = 0x80000000
  int mask = 1 << 31;
  int diff = x ^ y;
  // get diff's first bit
  diff |= (diff >> 1);
  diff |= (diff >> 2);
  diff |= (diff >> 4);
  diff |= (diff >> 8);
  diff |= (diff >> 16);
  diff &= ~(diff >> 1) | (1 << 31);

  return !(diff & (x ^ mask));
}

实现逻辑非, 即 !x.

合法操作符: ! ~ & ^ | + « », 最大步数: 12.

让非零的 x 变成 0xFFFFFFFF, 这样直接取非即可. 或者取非之后判断是否有 0.

int logicalNeg(int x) {
  int neg = ~x;
  neg = neg & (neg >> 1);
  neg = neg & (neg >> 2);
  neg = neg & (neg >> 4);
  neg = neg & (neg >> 8);
  neg = neg & (neg >> 16);
  return neg & 0x1;
}

返回补码中表示 x 的最小位数.

合法操作符: ! ~ & ^ | + « », 最大操作数: 90. 示例,

howManyBits(12) = 5

howManyBits(298) = 10

howManyBits(-5) = 4

howManyBits(0) = 1

howManyBits(-1) = 1

howManyBits(0x80000000) = 32

对于补码正数, 从最高位往最低位数, 第一个1出现的位置剩下的长度再加一个符号位就是能表示的最小位数. 对于负数, 取非之后能得到同样的结果.

然后利用前面条件判断的方法, 利用 0xFFFF0000 作为掩码, 逐渐二分查找第一个1出现的位置即可.

只用非和与实现异或 x^y.