Mcginn's Blog

CSAPP - datalab

字数统计: 1.9k阅读时长: 8 min
2020/02/14 Share

自动测试

  1. 使用 dlc 检测代码是否符合题目要求

    1
    unix> ./dlc bits.c

  2. 编译并调用自动测试程序

    1
    2
    unix> make
    unix> ./btest

题目

bitXor(x, y)

要求：仅使用 ~ 和 & 完成异或运算。

运算：~ &

做法：画出 & 运算符的真值表，配合 ~ 运算符易得。

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

tmin()

要求：返回二进制补码表示的最小整数。

运算： ! ~ & ^ | + << >>

做法：补码表示的最小整数为 $10\dots 0$，即符号位为 1，其余位为 0。

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

isTmax(x)

要求：判断 x 是否为补码表示的最大整数。

运算：! ~ & ^ | +

做法：当 x 为最大整数时，补码表示为 $01\dots 1$，即符号位为 0，其余位为 1，可得 x + 1 = ~x。

然而当 x = -1 时，前述等式也成立，因此需要排除掉这种情况。

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

allOddBits(x)

要求：判断 x 二进制表示下的奇数位是否全为 1。

运算：! ~ & ^ | + << >>

做法：规则允许使用最大为 0xFF 的整数，因此可使用 & 运算每 8 位合并 x 的所有位，然后使用 ^ 运算判断奇数位是否全为 1。

1
2
3
int allOddBits(int x) {
  return !(((x>>24) & (x>>16) & (x>>8) & x & 0xAA) ^ 0xAA);
}

negate(x)

要求：计算返回 -x。

运算：! ~ & ^ | + << >>

做法：首先将有符号数转换成无符号数以便于位运算处理。

相互转换的规则是：数值可能会改变，但位模式不变。因此，补码转换为无符号数为：

假设 $x \neq 0$，有 $x+(-x)=0$，两侧同加上 $2^w$ 并移项得

在 $x > 0$ 时，$-x$ 的补码表示与 $-x+2^w$ 的位模式相同，等于 $\sim x + 1$。

在 $x \le 0$ 时，$-x + 2^w$ 超出 $w$ 位二进制的表示范围，其结果为 $-x$ 的二进制表示。

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

isAsciiDigit(x)

要求：判断值 x 是否在范围 [0x30, 0x39] 中。

运算： ! ~ & ^ | + << >>

做法：首先前 $w - 4$ 位的值必须为 3，该判断容易实现。

剩余 4 位划分成 [0, 7] 和 [8, 9] 的两个区间来处理。

第 4 位为 0 时，剩余 3 位可为任意值，表示区间 [0, 7]。

第 4 位为 1 时，8 和 9 的二进制表示分别为 1000 和 1001，即高 3 位必须为 100。

利用掩码表示的思想，x 为 110111(0x37) 的子集或是 111001(0x39) 的子集。

1
2
3
int isAsciiDigit(int x) {
  return (!((x>>4)^3)) & (!(x^(x&0x37)) | !(x^(x&0x39)));
}

conditional(x, y, z)

要求：执行三目运算符 x ? y : z：当 x 不为 0 时，返回 y；否则返回 z。

运算：! ~ & ^ | + << >>

做法：核心思想是利用 x 得出位模式等于 -1（全为 1）的值，使用 & 运算和 ~ 运算得到 y 或 z 的位模式，最后使用 | 得到结果。

! 运算将 x 映射到 [0, 1] 区间，使用函数 $f(x)=!x + (-1)$ 取出 y，则 $\sim f(x)$ 取出 z。

当 $x \neq 0$ 时，$f(x)=-1$，其位模式全为 1，因此 $f(x) \& y = y$。

当 $x = 0$ 时，$f(x)=0$，其位模式全为 0，因此 $f(x)\&y=0$。

1
2
3
4
int conditional(int x, int y, int z) {
  x = !x + ~0;
  return (y & x) | (z & ~x);
}

isLessOrEqual(x, y)

要求：判断 x <= y。

运算：! ~ & ^ | + << >>

做法：将问题转换成判断 $a + b \le0$，新问题下需要注意溢出问题。

当 $a+b<0$ 时，其符号位为 1，因此执行 $a+b$ 并取出符号位可解决问题。但是，存在 $a+b$ 上溢出导致其符号位也为 1 的情况。

进一步地，当 $a$ 和 $b$ 符号位相同时，$a+b<0$ 当且仅当符号位均为 1。符号位不同时，$a+b$ 不存在溢出问题。

$a+b=0$ 特判 $x=y$ 即可。

注意取符号位是 &1 操作不可省略，因为机器使用了算术右移。

1
2
3
int isLessOrEqual(int x, int y) {
  return (!(x^y)) | ((x&~y)>>31&1) | ((!((x^y)>>31))&((x+(~y+1))>>31));
}

logicalNeg(x)

要求：计算 !x：当 x = 0 时返回 1；当 x ≠ 0 时返回 0。

运算：~ & ^ | + << >>

做法：当 $x \neq 0$ 时，$x|(-x)$ 的符号位必然为 1。

1
2
3
int logicalNeg(int x) {
  return ~(x|(~x+1))>>31&1;
}

howManyBits(x)

要求：使用二进制补码表示 x 的最少位数。

运算：! ~ & ^ | + << >>

做法：当 $x \ge 0$ 时，位数取决于 1 的最高位数；当 $x < 0$ 时，位数则取决于 0 的最高位数（根据补码表示的定义，符号位起连续的 1 可合并起来用一个位表示）。

首先考虑将负数取反，将问题统一成计算 1 的最高位，利用算术右移即可完成， 即 $x=x \oplus (x >>31)$。

然后使用二分法计算 1 的最高位：判断高 16 位是否大于 0，若大于 0 说明高 16 位中存在 1，否则 1 在低 16 位中。使用 conditional 函数更新 x（取出高 16 位或低 16 位）。迭代判断 8 位、4 位等等。

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
int howManyBits(int x) {
  int bit;
  int res = 1;
  x = x ^ (x >> 31);

  bit = !!(x >> 16) << 4;
  res = res + bit;
  x = x >> bit;

  bit = !!(x >> 8) << 3;
  res = res + bit;
  x = x >> bit;

  bit = !!(x >> 4) << 2;
  res = res + bit;
  x = x >> bit;

  bit = !!(x >> 2) << 1;
  res = res + bit;
  x = x >> bit;

  bit = !!(x >> 1);
  res = res + bit;
  x = x >> bit;

  return x + res;
}

floatScale2(uf)

要求：计算 2 * uf，若 uf 为特殊值值时，直接返回 uf。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：这道题需要对浮点数表示比较了解，单精度（float）表示包括：1 位符号，8 位阶码，23 位尾数。这里使用 e 表示阶码的无符号数，B 表示阶码的偏置值，f 表示尾数值。

  1. 当 e 全 0 时，表示非规格化的值，真实值 $V=f\times 2^{1-B}$。

    乘上系数 2 时，阶码是否变动看 2f 是否大于等于 1，即 f 最高位是否为 1。由于阶码在尾数的高位，该情况下位数左移 1 位即可。

  2. 当 e 不全 0 也不全 1 时，表示规格化的值，真实值 $V=(1+f)\times 2^{e - B}$。

    阶码 + 1 即可。

  3. 当 e 全 1 时，表示特殊值。

1
2
3
4
5
6
7
8
unsigned floatScale2(unsigned uf) {
  unsigned s = uf >> 31 & 1;
  unsigned e = uf >> 23 & 0xff;
  unsigned f = uf ^ (s << 31) ^ (e << 23);
  if (!(e^0xff)) return uf;
  if (!e) return (s << 31) | (f << 1);
  return (s << 31) | ((e + 1) << 23) | f;
}

floatFloat2Int(uf)

要求：将浮点数 uf 转换成整数。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：当浮点数是 0 和规格化的值时，才有可能用整数表示，其余部分注意整数表示范围即可。

1
2
3
4
5
6
7
8
9
10
11
12
int floatFloat2Int(unsigned uf) {
  int s = uf >> 31 & 1;
  int e = uf >> 23 & 0xff;
  int f = uf ^ (s << 31) ^ (e << 23);
  if (!(e | f)) return 0;
  e = e - 0x7f;
  if (e < 0) return 0;
  if (e > 30 + (s & !f)) return 0x80000000u;
  f = ((1 << 23) | f) >> (23 - e);
  if (s) return -f;
  return f;
}

floatPower2(x)

要求：使用浮点数表示 2^x。无法表示时：过小返回 0，过大返回 +INF。

运算：Integer/unsigned 相关运算；||，&&，if 和 while 等判断语句。

做法：

1
2
3
4
5
unsigned floatPower2(int x) {
  x = x + 0x7f;
  if (x < 0) return 0;
  return x < 0xff ? x << 23 : 0x7f800000u;
}
CATALOG
  1. 1. 自动测试
  2. 2. 题目
    1. 2.1. bitXor(x, y)
    2. 2.2. tmin()
    3. 2.3. isTmax(x)
    4. 2.4. allOddBits(x)
    5. 2.5. negate(x)
    6. 2.6. isAsciiDigit(x)
    7. 2.7. conditional(x, y, z)
    8. 2.8. isLessOrEqual(x, y)
    9. 2.9. logicalNeg(x)
    10. 2.10. howManyBits(x)
    11. 2.11. floatScale2(uf)
    12. 2.12. floatFloat2Int(uf)
    13. 2.13. floatPower2(x)
Total : 31
2021
2020
2019
2018
AhoCorasick AC自动机 domjudge DR KMP ICPC 贪心 vim git bash polya 斜率优化 SW