CSAPP - datalab

 2020/02/14 

自动测试

使用 dlc 检测代码是否符合题目要求
1
unix> ./dlc bits.c
编译并调用自动测试程序
1
2
unix> make
unix> ./btest

题目

bitXor(x, y)

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

运算：~ &

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

1
2
3

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

tmin()

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

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

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

1
2
3

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

isTmax(x)

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

运算：! ~ & ^ | +

做法：当 x 为最大整数时，补码表示为，即符号位为 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。

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

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

相互转换的规则是：数值可能会改变，但位模式不变。因此，补码转换为无符号数为：假设，有，两侧同加上并移项得在时，的补码表示与的位模式相同，等于。

在时，超出位二进制的表示范围，其结果为的二进制表示。

1
2
3

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

isAsciiDigit(x)

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

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

做法：首先前位的值必须为 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] 区间，使用函数取出 y，则取出 z。

当时，，其位模式全为 1，因此。

当时，，其位模式全为 0，因此。

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

isLessOrEqual(x, y)

要求：判断 x <= y。

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

做法：将问题转换成判断，新问题下需要注意溢出问题。

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

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

特判即可。

注意取符号位是 &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。

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

做法：当时，的符号位必然为 1。

1
2
3

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

howManyBits(x)

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

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

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

首先考虑将负数取反，将问题统一成计算 1 的最高位，利用算术右移即可完成，即。

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

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 表示尾数值。

当 e 全 0 时，表示非规格化的值，真实值。

乘上系数 2 时，阶码是否变动看 2f 是否大于等于 1，即 f 最高位是否为 1。由于阶码在尾数的高位，该情况下位数左移 1 位即可。
当 e 不全 0 也不全 1 时，表示规格化的值，真实值。

阶码 + 1 即可。
当 e 全 1 时，表示特殊值。

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 和规格化的值时，才有可能用整数表示，其余部分注意整数表示范围即可。

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 等判断语句。

做法：

unsigned floatPower2(int x) {
  x = x + 0x7f;
  if (x < 0) return 0;
  return x < 0xff ? x << 23 : 0x7f800000u;
}

原文作者：Mcginn

原文链接：http://mcginn7.github.io/2020/02/14/CSAPP-datalab/

发表日期：February 14th 2020, 10:55:06 pm

更新日期：May 4th 2024, 5:07:17 pm

Next Post

CSAPP - bomblab
Previous Post

回文分解算法

CATALOG

1. 自动测试
2. 题目