近来开始读 CS:APP3e 第二章，但干看书做课后题太乏味，于是提前把 DataLab 拉出来练练。不一定是优解，趁热记录一下思路吧。

如果读者是那种还没做完 lab 就想借鉴答案的，还请收手，坚持独立完成吧，正如课程作者所说，Don't cheat, even the act of searching is checting.

bitXor

1
2
3
4
5
6
7
8
9
10







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

简单的公式可以写作 (x & y) | (~x & y) ，但题目要求只能用 ~ & 两种操作，换句话就是考察用 ~ & 来实现 | 操作，和逻辑与或非类似。

tmin

1
2
3
4
5
6
7
8
9






int tmin(void) {
  return 1 << 31;
}

这个题目就是计算出 0x80000000 ，基本的移位操作即可，不用复杂化。

isTmax

1
2
3
4
5
6
7
8
9
10







int isTmax(int x) {
  return !(~(1 << 31) ^ x);
}

上面已经知道怎么获取 TMIN，TMAX 可以用 ~TMIN 表示，因此主要考察两个数是否相等 —— ^。

错误更正

感谢 @nerrons 兄指正

前面的解法忽略了操作符的限制，是不合题意的。故更换思路：由于 TMAX + 1 可得到 TMIN，若 x 为 TMAX，则 x + 1 + x 结果为 0。

但直接这样写无法通过检测程序，是因为 0xffffffff 同样满足 x + 1 + x 为 0 的特性，需要将该情况排除。

1
2
3
int isTmax(int x) {
  return !(~((x + 1) + x) | !(x + 1));
}

allOddBits

1
2
3
4
5
6
7
8
9
10
11
12








int allOddBits(int x) {
  int odd = (0xAA << 24) + (0xAA << 16) + (0xAA << 8) + 0xAA;
  return !((x & odd) ^ odd);
}

先构造 0xAAAAAAAA，利用 & 操作将所有奇数位提出来，再和已构造的数判等。

negate

1
2
3
4
5
6
7
8
9
10







int negate(int x) {
  return ~x + 1;
}

二进制基础扎实的话，可以秒出结果。

isAsciiDigit

1
2
3
4
5
6
7
8
9
10
11
12
13
14









int isAsciiDigit(int x) {
  
  int TMIN = 1 << 31;
  return !((x + ~0x30 + 1) & TMIN) & !((0x39 + ~x + 1) & TMIN);
}

主要思路可以用逻辑运算表示，(x - 0x30 >= 0) && (0x39 - x) >=0，这里新概念是如何判断数值是否小于 0。

conditional

1
2
3
4
5
6
7
8
9
10
11
12







int conditional(int x, int y, int z) {
  int f = ~(!x) + 1;
  int of = ~f;
  return ((f ^ y) & of) | ((of ^ z) & f);
}

这里我用 ~(!x) + 1 构造了 x 的类布尔表示，如果 x 为真，表达式结果为 0，反之表达式结果为 ~0。

isLessOrEqual

1
2
3
4
5
6
7
8
9
10
11
12
13
14







int isLessOrEqual(int x, int y) {
  
  int signX = (x >> 31) & 1;
  int signY = (y >> 31) & 1;
  int signXSubY = ((y + ~x + 1) >> 31) & 1;
  return (signX & ~signY) | (!(signX ^ signY) & !signXSubY);
}

核心是判断 y + (-x) >= 0。一开始我做题时被 0x80000000 边界条件烦到了，所以将其考虑进了判断条件。

具体做法是判断 Y 等于 TMIN 时返回 0，X 等于 TMIN 时返回 1。此外也考虑了若 x 为负 y 为 正返回 1，x 为正 y 为负返回 0。

这样想得太复杂了，使用的操作有点多，而题目对 ops 限制是 24，担心过不了 dlc 的语法检查。 所以又花更多时间想出更简单的方法。用逻辑操作可以写作 (y >=0 && x <0) || ((x * y >= 0) && (y + (-x) >= 0))。不过我后来在 linux 上运行了一下第一种方法，dlc 并没有报错。

logicalNeg

1
2
3
4
5
6
7
8
9
10
11
12
13








int logicalNeg(int x) {
  int sign = (x >> 31) & 1;
  int TMAX = ~(1 << 31);
  return (sign ^ 1) & ((((x + TMAX) >> 31) & 1) ^ 1);
}

x 小于 0 时结果为 1，否则检查 x + TMAX 是否进位为负数。

howManyBits

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38












int howManyBits(int x) {
  int sign = (x >> 31) & 1;
  int f = ~(!sign) + 1;
  int of = ~f;
  



  x = ((f ^ ~x) & of) | ((of ^ x) & f);
  





  x |= (x << 1);
  int n = 0;
  
  n += (!!(x & (~0 << (n + 16)))) << 4;
  n += (!!(x & (~0 << (n + 8)))) << 3;
  n += (!!(x & (~0 << (n + 4)))) << 2;
  n += (!!(x & (~0 << (n + 2)))) << 1;
  n += !!(x & (~0 << (n + 1)));
  
  return n + 1;
}

这里我利用了之前 conditional 的做法，讲 x 为负的情况排除掉，统一处理正整数。统计位数可以采取二分法查找最高位的 1，但做了几轮测试就会发现二分法存在漏位的问题。

不过这只在偶数位发生，奇数位不受影响。因此为了排除这个影响，我暴力地用 x |= (x << 1) 的办法让最高位的 1 左移 1 位。

floatScale2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22











unsigned floatScale2(unsigned uf) {
  int exp = (uf >> 23) & 0xFF;
  
  if (exp == 0xFF)
    return uf;
  
  if (exp == 0)
    return ((uf & 0x007fffff) << 1) | (uf & (1 << 31));
  
  return uf + (1 << 23);
}

只需要简单地取出指数部分，甚至不需要拆解，排除 INF、NaN、非规格化的情况之后，剩下规格化的处理是指数部分的位进一。

floatFloat2Int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26












int floatFloat2Int(unsigned uf) {
  int TMIN = 1 << 31;
  int exp = ((uf >> 23) & 0xFF) - 127;
  
  if (exp > 31)
    return TMIN;
  if (exp < 0)
    return 0;
  int frac = (uf & 0x007fffff) | 0x00800000;
  
  int f = (exp > 23) ? (frac << (exp - 23)) : (frac >> (23 - exp));
  
  return (uf & TMIN) ? -f : f;
}

首先拆分单精度浮点数的指数和基数，指数部分减去 127 偏移量，用来排除临界条件。大于 31 时，超过 32 位 Two’s Complement 的最大范围，小于 0 则忽略不计，根据题意分别返回 0x80000000 和 0。

之后根据指数部分是否大于 23 来判断小数点位置。如果大于，说明小数部分全部在小数点左边，需要左移；如果小于则需要右移。最后补上符号位。

floatPower2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23













unsigned floatPower2(int x) {
  int exp = x + 127;
  
  if (exp <= 0)
    return 0;
  
  if (exp >= 0xFF)
    return 0x7f800000;
  return exp << 23;
}

加 127 得到指数阶码，超过表示范围则返回 0 和 INF。由于小数点后面都是 0，只需左移指数部分。

小结

现在 Mac 已无法运行 32 位的代码检查工具 dlc，不过可以先跑逻辑测试，等写完再放到 Linux 机跑一遍 dlc 测试。

原以为这点知识在学校掌握得还可以，随书习题和前几道 lab 也的确简单，实际做到后面有许多卡壳的点，浮点数的概念都模糊了，真是一边翻书一边做，快两天才完成。书本的这章我还是甭跳了，继续刷去吧。