最近本来在看 CSAPP 后面的内容，但突然发现自己前面可能还有一些知识掌握不完全，因此做一下 Lab 检验一下。

准备工作

在 CSAPP 的官网上找到 Lab，下载 Self-Study Handout。
在下载目录下解压文件

tar -xf datalab-handout.tar

尝试执行自动测评脚本driver.pl结果发现没有32位环境，于是用dnf安装需要的库，折腾了一会发现还是不太行。请教了大佬 jyi2ya，他告诉我可以直接在makefile里面把编译条件改为-m64。

题目与题解

int 部分

bitXor

只用~和&实现^

可以使用德摩根定理秒杀。

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

tmin

使用位运算获取补码的最小值

由于题目已经告诉了我们机器环境，我们可以认为int类型是占八个字节。

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

isTmax

使用位运算获取判断是否是补码的最大值

这题相较上题有一定的技巧。主要思路为把补码的每一位变为1，这样就可以很方便地得到0或非0的值。在转换的过程中要注意到-1同样适用，所以要对-1进行特判。

int isTmax(int x) {
  // 如果是0b111...111或者0b011...111就能变为0b000...000
  int check = ~(x + 1 + x);
  // 如果是-1则结果为1，排除掉
  int except = !(x + 1);
  return !(check | except);
}

allOddBits

判断所有奇数位是否都为1

一开始的想法是直接暴力判断每个奇数位是否为1（先移位然后进行逻辑与运算），但是这样应该得不到性能分。于是我想到了类似于二分法的思想，每次对半比较，最后只需要七次操作捏。

int allOddBits(int x) {
  x &= (x >> 16);
  x &= (x >> 8);
  return !(x & 0xaa ^ 0xaa);
}

negate

不使用-操作符，求-x

运用补码的基础知识得到答案。

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

isAsciiDigit

计算输入值是否是数字0-9的 ASCII 值。

一开始打算先判断前多少多少位是不是0，后面是否满足0x30 <= x <= 0x39，后来一想发现这样好复杂，可以直接通过范围判断。

可以使用一个小技巧，这个技巧也可以优化分支预测。

if (x >= a && x <= b) {
  do_something();
}
// 等价于
if ((x - a) | (b - x) >= ) {
  do_something();
}

这里不能使用-，但是可以利用前面题目的结论，通过取反和加法代替减法。

于是我们得到了答案：

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

conditional

通过位运算模拟三目运算

不难想到：一个数和0x0进行逻辑与操作的结果是0x0，一个数和~0x0进行逻辑与操作的结果是本身。因此我们可以构造一个与x有关的掩码，当x为真时就是0xffffffff，否则为0x0。

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

isLessOrEqual

通过位运算模拟小于等于

将两个数移到一边变为减法运算，再把减法运算变为加上绝对值的加法运算，最后判断最高位是否为0即可。

int isLessOrEqual(int x, int y) {
  return !(y + (~x + 1) & (1 << 31));
}

结果这个代码被朋友叉掉了，因为我没有考虑到溢出的情况，所以要加上对一个是正数一个是负数的特判。

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

logicalNeg

通过位运算模拟逻辑非

我很自然地想到了这样的代码，结果发现没有拿到性能分，刚好比要求多一个操作。

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

于是我分析这段垃圾代码，发现x ^= ~0就占用了两步操作，而且有更好的替代方法。

依然使用类似二分法的思想，同时以使用或操作为主，就能节约操作了。代码如下：

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

howManyBits

求最少用多少个位可以表示出给定数字

刚开始做这题时，我看着题目的例子搞不懂为啥-1只需要一位。最后我的理解就是，题目想问的是“最少用多少个位可以表示从0到给定的数字”，因此如果给出负数我们就不需要考虑正数，反之同理。

所以这道题转化为了求 $log_2x$ 。

还是可以将用类似二分的思想解题。首先判断前16位是否有1，如果有就要加上16，同时下一次的移位要多移动16位，依此类推。每次加上的权不同，代表这次判断的一共有n位（16、8、4、2、1）

int howManyBits(int x) {
  int mask, b16, b8, b4, b2, b1, b0;
  mask = x >> 31;
  x = (mask & ~x) | (~mask & x);
  b16 = !!(x >> 16) << 4;
  x = x >> b16;
  b8 = !!(x >> 8) << 3;
  x = x >> b8;
  b4 = !!(x >> 4) << 2;
  x = x >> b4;
  b2 = !!(x >> 2) << 1;
  x = x >> b2;
  b1 = !!(x >> 1);
  x = x >> b1;
  b0 = x;
  return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}

float 部分

浮点数的题目比较简单，只考察其结构而不是运算。

为了位运算方便，题目中给出的函数参数和返回值都是与float长度相同的unsigned int或者int

floatScale2

求一个浮点数乘2

首先取出符号sign、尾数frac、阶码exp。
如果阶码是0，说明是一个非规格化的浮点数，由于浮点数的分规格化到规格化的过渡是连续的，因此尾数向左移动一位变成规格化浮点数不是特殊情况。
如果阶码全为1，说明是无穷大，直接原样返回即可。
给阶码加上1，即是给变量exp加上0x800000。
如果溢出了变为无穷大，就要将尾数变为0，否则就是NaN了。
将三部分拼接后返回。

unsigned floatScale2(unsigned uf) {
  unsigned sign = uf & 0x80000000;
  unsigned exp = uf & 0x7f800000;
  unsigned frac = uf & 0x007fffff;
  if (exp == 0)
    return sign | uf << 1;
  if (exp == 0x7f800000)
    return uf;
  exp += 0x00800000;
  if (exp == 0x7f800000)
    frac = 0;
  return sign | exp | frac;
}

floatFloat2Int

将一个浮点数转换为整型数

在 CSAPP 中介绍过几种舍入的方法，在计算中向偶数（奇数）位舍入会减小误差，而在类型转换中，使用向零舍入会比较方便。

首先将符号、尾数、阶码取出来，为了加减法计算方便，对阶码进行了移位，并加上了127。
尾数的第24位置为1，因为在规格化数中就是1.x的形式。而非规格化数舍入变为0，不需要考虑其尾数。
如果阶小于0，直接返回0。
如果阶大于31，说明是无穷大。
其余情况就是对加上1.x（x为尾数）进行移位，由于尾数长24位，因此有方向和绝对值要注意。
带上符号后返回答案。

int floatFloat2Int(unsigned uf) {
  int ans;
  int sign = uf & 0x80000000;
  int exp = ((uf >> 23) & 0xff) -127;
  int frac = (uf & 0x007fffff) | 0x00800000;
  if (exp < 0)
    return 0;
  if (exp > 31)
    return 0x80000000;
  if (exp < 23)
    ans = frac >> (23 - exp);
  else
    ans = frac << (exp - 23);
  return sign ? ~ans + 1 : ans;
}

floatPower2

求$2.0^x$

利用一个结论：最小的非规格化数是 $2^{-23}*2^{-126}$ ，最大的非规格化数是 $(1-u)*2^{-126}$ ，最小的规格化数是 $2^{-126}$ ，最大规格化数是 $(2-u)*2^{127}$，其中 $u$ 为无穷小。

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

总结

测评结果

Correctness Results	Perf Results
Points	Rating	Errors	Points	Ops	Puzzle
1	1	0	2	8	bitXor
1	1	0	2	1	tmin
1	1	0	2	7	isTmax
2	2	0	2	7	allOddBits
2	2	0	2	2	negate
3	3	0	2	10	isAsciiDigit
3	3	0	2	8	conditional
3	3	0	2	6	isLessOrEqual
4	4	0	2	12	logicalNeg
4	4	0	2	36	howManyBits
4	4	0	2	11	floatScale2
4	4	0	2	15	floatFloat2Int
4	4	0	2	10	floatPower2

Score = 62/62 [36/36 Corr + 26/26 Perf] (133 total operators)

做了 CSAPP 的 Data Lab 还是收获良多的：

发现自己之前学习的位运算和浮点数的知识还有不少漏洞，幸好补起来了。
在做这种限制操作的题目时，一开始还是会感觉很不适应，疯狂地想写分支判断等操作。坚持下来之后就有不小的提高，对抽象能力和写更高性能的代码都有帮助。
Lab 中给出的makefile开的编译选项给我报了很多警告，让我发现我的代码习惯不是很好，还有很大进步空间。

准备工作#

题目与题解#

int 部分#

bitXor#

tmin#

isTmax#

allOddBits#

negate#

isAsciiDigit#

conditional#

isLessOrEqual#

logicalNeg#

howManyBits#

float 部分#

floatScale2#

floatFloat2Int#

floatPower2#

总结#