CSAPP Lab-1 DATALAB

最近看完了 CSAPP 整本书，发现官网上还有 11 次实验可以做。

UPD：好像只有 9 个，因为有两个是旧版本的，可以被新版的替代掉。

UPD：好像只有 8 个，performance 也算是旧的实验了，但是没有明确指出。

Lab 地址：

http://csapp.cs.cmu.edu/3e/labs.htmlhttp://csapp.cs.cmu.edu/3e/labs.html

bitXor(x,y)

题意

任务： $x$ 异或 $y$ （x ^ y）

允许使用的运算符：~ &

操作数限制： $14$

Solution

对于每一位分别考虑。假设 $P, Q$ 分别是 $x, y$ 的某一个对应位，那么这一位上的异或和就是

\begin{aligned} P \oplus Q &= \overline{P}Q + P\overline{Q}\\ &= \overline{\overline{\overline{P}Q}\ \overline{P\overline{Q}}} \end{aligned}

Code

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

共 $8$ 次操作。

tmin()

题意

任务：二进制补码下最小的 int 类型的数

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $4$

Solution

这个题目非常简单，答案就是 $-2^{31}$ ，在 int 补码下是 $1$ 后面接 $31$ 个零，只有最高位为 $1$ ，也就是 1 << 31。

Code

1
2
3

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

共 $1$ 次操作。

isTmax(x)

题意

任务：判断 $x$ 是不是补码表示下最大的 int 类型数。

允许使用的运算符：! ~ & ^ | +

操作数限制： $10$

Solution

我的做法比较奇怪吧。

最大的 int 类型数也就是 $2^{31} - 1$ （0x7fffffff）。

如果 $x$ 满足要求，那么 $x+1$ 就是 $-2^{32}$ （0x80000000），等于 ~x。可以使用 ~((x + 1) ^ x) = 0 来判断。

但是需要注意的是， $-1$ （0xffffffff）也满足这个性质，因此需要特判这种情况。可以使用 !(x + 1) = 1 来判断。

因此综合起来，用 $a$ 表示 $x+1$ ，最后的答案就是 !((~(a ^ x)) | !a)。

Code

int isTmax(int x) {
  int a = x + 1;
  return !((~(a ^ x)) | !a);
}

共 $6$ 次操作。

allOddBits(x)

题意

任务：判断 $x$ 的奇数位是否都是 $1$ 。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $12$

Solution

这题难住了我不短的时间。

其实是一开始没有想到直接构造出所有奇数位的掩码。

题目限制只能使用 $0$ 和 $255$ 之间的整数，所以可以使用 0xAA（10101010）扩展两次得到 $32$ 位的奇数位掩码。

假设 a = 0xAA，那么使用 (a << 8) + a 即可得到 $16$ 位奇数位掩码，将结果存进 $a$ 中，再使用 msk = (a << 16) + a 即可得到完整 $32$ 位的掩码。

使用 x & msk 就是 $x$ 所有奇数位，使用 ^ 与 $msk$ 进行对比，异或结果为 $0$ 说明相同，再取非即可得到答案。

Code

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

共 $7$ 次操作。

negate(x)

题意

任务：返回 $-x$ 的补码。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $5$

Solution

经典问题，答案就是取反再加 $1$ ，也就是 $(~x) + 1$ ，不解释。

Code

1
2
3

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

共 $2$ 次操作。

isAsciDigit(x)

题意

任务：判断 $x$ 对应的 ASCII 码是不是数字字符（也就是 0x30 到 0x39` 之间）。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $15$

题解

首先判断高 $28$ 位是不是 0x3。使用 !((x >> 4) ^ 3 判断。

然后判断低 $4$ 位是不是 1001 及以下。考虑到不合法的分别有 1010, 1011, 1100, 1110, 1111 这些数，满足第 $3$ 位（最低位为第 $0$ 位）为 $1$ ，且第 $2, 3$ 位至少有一位为 $1$ 。只要这两个条件有一个不满足就可以认为合法。

第 $3$ 位不为 $1$ 可以用 !(x & 8) 判断。

第 $2, 3$ 位不存在一位为 $1$ 可以用 !(x & 6) 判断（6 = 0110）。

Code

int isAsciiDigit(int x) {
  int pre = !((x >> 4) ^ 3);
  return pre & (!(x & 8) | !(x & 6));
}

共 $9$ 次操作。

conditional(x, y, z)

题意

任务：返回 C 语言 x ? y : z 的结果。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $16$

Solution

假设我们可以把 $x$ 扩展成一个 $k$ ，满足如果 $x$ 为真，那么 k = 111...1，否则 $k = 000...0$ ，那么我们可以把答案表示成 (k & y) | ((~k) & z)。

考虑怎么扩展。我们可以用 $!x$ 得到 $x$ 的逻辑值的非，只有末位可能为 $1$ ，高位全部为 $0$ ，作为初始的 $k$ ，然后倍增构造。

使用 k = (k << 1) | k 构造两位版本，然后 k = (k << 2) | k 构造四位，以此类推，即可得到完整的 $k$ 。

当然，最后得到的 $k$ 与我们之前假设的相反，为 !x 的扩展，因此答案表达式也需要稍作改变。

Code

int conditional(int x, int y, int z) {
  int k = !x;
  k = k | (k << 1);
  k = k | (k << 2);
  k = k | (k << 4);
  k = k | (k << 8);
  k = k | (k << 16);
  return ((~k) & y) | (k & z);
}

共 $15$ 次操作。

isLessOrEqual(x, y)

题意

任务：判断 int 类型下 $x$ 是否小于等于 $y$ 。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $24$

Solution

一般来说，只需要判断 $x - y$ 的正负性即可。 $x - y$ 可以使用 $x$ 加上 $-y$ 的补码得到，也就是 x + (~y) + 1。如果 $x - y = 0$ 需要特殊判断。

但是，如果 $x - y$ 发生溢出，那么这样判断就会不准确了。因此我们可以先判断 $x, y$ 各自的符号，只有在同号的时候我们才判断 $x-y$ 。如果 $x, y$ 符号位不同，可以直接判断结果。

一个数的符号位可以通过 (x >> 31) & 1 获得。

具体地，假设 $z = x - y$ ，nx, ny, nz 分别为 $x, y, z$ 的符号位，f1 表示 $x - y = 0$ 的逻辑值。那么如果 $f1$ 为真，或者 $x$ 负 $y$ 正（nx & !ny）答案就是 1，此外，除非 nx 和 ny 相同（nx ^ !ny）才会需要 $z$ 的符号位。

结果就是 f1 | (nx & !ny) | ((nx ^ !ny) & z)，其中 !ny 重复使用，可以增加一个中间变量来节省操作数。

Code

int isLessOrEqual(int x, int y) {
  int nx = (x >> 31) & 1;
  int ny = (y >> 31) & 1;
  int nny = !ny;
  int z = x + (~y) + 1;
  int f1 = !z;
  z = (z >> 31) & 1;
  return f1 | (nx & nny) | ((nx ^ nny) & z);
}

共 $16$ 次操作。

logicalNeg(x)

题意

任务：使用逻辑非，即 !x。

允许使用的运算符：~ & ^ | + << >>

操作数限制： $12$

Solution

和之前 conditional 这个题中构造 $k$ 的过程很相似，不是要反过来做。

每次我们把 $x$ 高位的一半和低位的一半做按位或（|），然后假装 $x$ 少了一半位，那么当 $x$ 只剩一位的时候， $x$ 就是所有位的或了。

那么只需要将末位取出，然后 ^ 1 构造出非。

Code

int logicalNeg(int x) {
  x = (x >> 16) | x;
  x = (x >> 8) | x;
  x = (x >> 4) | x;
  x = (x >> 2) | x;
  x = (x >> 1) | x;
  return (x & 1) ^ 1;
}

共 $12$ 次操作。

howManyBits(x)

题意

任务：返回补码形式下，表达 $x$ 最少需要多少位。

允许使用的运算符：! ~ & ^ | + << >>

操作数限制： $90$

Solution

愣是读题读了半天才理解……这里说的补码形式是，一个二进制串最高位为符号位，剩下的使用补码构造。

那么如果 $x$ 是负数，我们将之取反，得到的结果不变。

然后我们只需要找到最高的一个 $1$ 的位置，倍增统计即可。

具体地，假设 $x$ 现在是 $32$ 位，我们取出最高的 $16$ 位，判断是否全是 $0$ ，如果是的话就将 $x$ 设置为低 $16$ 位，否则将答案加上 $16$ 然后将 $x$ 设置为高 $16$ 位。

位数折半，重复以上过程直到最后一位做完。

答案再上加 $1$ 的符号位即可。

Code

int howManyBits(int x) {
  int f, p;
  int ans = 0;
  int s = x >> 31;
  x = (~s & x) | (s & ~x);
  f = !!(x >> 16), p = f << 4;
  ans = ans + p, x = x >> p;
  f = !!(x >> 8), p = f << 3;
  ans = ans + p, x = x >> p;
  f = !!(x >> 4), p = f << 2;
  ans = ans + p, x = x >> p;
  f = !!(x >> 2), p = f << 1;
  ans = ans + p, x = x >> p;
  f = !!(x >> 1), p = f;
  ans = ans + p, x = x >> p;
  f = x, p = f;
  ans = ans + p + 1;
  return ans;
}

共 $37$ 次操作。

floatScale2(uf)

题意

任务：以 unsigned 类型给出一个 $32$ 位浮点数 $uf$ 的位级表示，求出 $uf \cdot 2$ 的位级表示。

允许使用的运算符：所有整数操作符，包括 &&, || 和 if, while。

操作数限制： $30$

Solution

首先用下面的代码求出符号、尾数和阶码。

1
2
3

int s = uf & (1 << 31);
int f = uf & 0x7fffff;
int e = (uf >> 23) & 0xFF;

如果为特殊值（无穷大和 NaN），那么保持不变返回即可。

如果为非规格数，uf << 1 即可得到符号位之外的正确结果（如果尾数部分溢出了会刚好溢出到阶码中），接上符号位即可得到答案。

如果为规格数，那么将阶码 $+1$ ，如果阶码变成了 0xFF，答案就是无穷大，否则将符号、新的阶码和尾数拼接即可。

Code

unsigned floatScale2(unsigned uf) {
  int s = uf & (1 << 31);
  int f = uf & 0x7fffff;
  int e = (uf >> 23) & 0xFF;
  if (e == 0xFF) return uf;
  if (e == 0) return (uf << 1) | s;
  ++e;
  if (e == 0xFF) return s | 0x7f800000;
  return s | (e << 23) | f;
}

共 $14$ 次操作。

floatFloat2Int(uf)

题意

任务：以 unsigned 类型给出一个 $32$ 位浮点数 $uf$ 的位级表示，求出 (int)uf 的结果。

允许使用的运算符：所有整数操作符，包括 &&, || 和 if, while。

操作数限制： $30$

Solution

将阶码 $- 127$ 得到真正的指数 e。

如果 $e < 0$ ，那么说明 $|uf| < 1$ ，答案是 $0$ 。

如果 $e \geq 31$ ，那么说明 $|uf| \geq 2^{31}$ ，超过了 int 的表示范围，返回题目要求的 0x80000000u。（ps：不用特判 $uf = -2^{31}$ 的情况，因为 0x80000000u 刚好就是对应的值）

否则，我们取出尾数，再在最前面加上一个 $1$ （浮点表示法中被省略的 $1$ ），就是尾数表示的值乘上 $2^{23}$ 。根据浮点数的结构，依据 $e$ 和 $23$ 的大小将尾数左右移即可。如果 $e \geq 23$ ，那么将尾数左移 $e - 23$ 位，否则右移 $23 - e$ 位。

Code

int floatFloat2Int(unsigned uf) {
  int s = uf & (1 << 31);
  int f = (uf & 0x7fffff) | 0x800000;
  int e = ((uf >> 23) & 0xFF) - 127;
  if (e < 0) return 0;
  if (e >= 31) return 0x80000000u;
  if (e >= 23) f <<= e - 23;
  else f >>= 23 - e;
  if (s) f = -f;
  return f;
}

共 $15$ 次操作。

floatPower2(x)

题意

任务： $2^x$ 的浮点数位级表示。

允许使用的运算符：所有整数操作符，包括 &&, || 和 if, while。

操作数限制： $30$

Solution

浮点数阶码的表示范围是 $-126$ 到 $127$ 。

如果 $x > 127$ ，那么答案就是无穷大。

否则，如果 $x \geq -126$ ，那么可以用规格数表示，将 $x + 127$ 嵌进 $23$ 到 $30$ 位上即可（(x + 127) << 23）。

否则，如果 $x \geq -126 - 23 = -149$ ，那么 $x$ 可以用非规格数表示，因为非规格数尾数部分第 $i$ 位表示 $2^{i - 23} \times 2^{-126}$ ，因此答案就是 1 << (x + 149)。

否则无法表示，返回 $0$ 。

Code

unsigned floatPower2(int x) {
  if (x > 127) return 0x7f800000;
  if (x >= -126) return (x + 127) << 23;
  if (x >= -149) return 1 << (x + 149);
  return 0;
}

共 $9$ 次操作。

ps：这个问题测试数据好像特别多，在时间限制内评测不完，需要在 btest.c 中将 TIMEOUT_LIMIT 宏改大一些，比如 $20$ 。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。