前言:

最近在看完《深入理解计算机系统》前两章之后，也将其第一个Lab——DataLab完成了，于是来对此做一个记录。DataLab主要是对整型和浮点型的实验，其中对条件语句、算数运算还有逻辑运算进行了不同的限制。

实验环境的搭建：

首先由于其实验环境是unix，我使用的是VMware Workstation + Ubuntu来搭建实验环境。VMware虚拟机和Ubuntu的安装可以看这篇博客VMware Ubuntu安装详细过程（详细图解）_vmware安装ubuntu-CSDN博客，具体搭建过程可看这篇博客：【CSAPP】Lab0 - 环境配置_csapp 3e操作环境搭建_Luqwera的博客-CSDN博客。

如果不想安装虚拟机，也可以使用Docker里的Linux容器来搭建，具体的操作过程可看这篇博客超详解 CS:APP:Lab1-DataLab_optional cmd line args-CSDN博客。

完成环境的搭建后便可以开始做DataLab了。

问题描述及解析：

1.bitXor

题目的意思就是只使用 ~（取反符号）和 & （与运算符）来实现 ^ (异或)。

看到这个，首先想到了数字逻辑里的一个公式：

就是 “同或的非” = “异或”，但是里面有“或”运算符，所以要再使用一下德摩根定律：

就可以解决这道题了。

/* 
 * bitXor - x^y using only ~ and & 
 *   Example: bitXor(4, 5) = 1
 *   Legal ops: ~ &
 *   Max ops: 14
 *   Rating: 1
 */
int bitXor(int x, int y) {
  return ~(x & y) & ~(~x & ~y);
}

2.tmin

题目的意思就是返回对32位 int 最小的二补数（就是补码）。下面是 n 比特的二补数系统中几个特别的数字：

二补数	实际数字	备注
0111 1111 …. 1111	$2^{n-1} -1$	最大正数
…	…
0000 0000 …. 0001	1
0000 0000 …. 0000	0
1111 1111 …. 1111	-1
…	…
1000 0000 …. 0000	$-2^{n-1}$	最小负数

所以在32位的环境下，补码的最小值就是：Tmin = $-2^{32-1}$$=-2^{31}$。用十六进制表示就是0x80000000，及将 1 向左移 31位。这样就可以解决了。

/* 
 * tmin - return minimum two's complement integer 
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
int tmin(void) {
  return 1<<31;
}

3.isTmax

这道题目需要你对输入的 x 进行判断是否为最大的补码，如果是就返回 1 ，不是则返回 0 。

由上一题可以知道，在32位的环境中最大的补码为 $2^{31}-1$ 及 0111 1111 …. 1111，所以我们可以从这个最大数入手。

首先可以发现 Tmax = 0111 1111 …. 1111 在加上一个 1 后会直接溢出变成 1000 0000 …. 0000，然后再对其取反后，就又变回了原来的 Tmax，故可以得到~(Tmax+1)= Tmax，因此，我们现在只需要判断~(x+1)与 x 是否相等就可以得出结论。但是题目限制无法使用等号，所以就可以利用异或运算的一个特性，即 x⊕x=0 ，就是两个相同的数进行异或后结果为 0 ，这里需要相同情况下返回 1，故要使用 ! 符号。所以最后组合在一起就是:

return !(~(x+1)^x);

但是当你保存检测后发现没有通过。

仔细看了错误后会发现当 x = -1 时，返回的是 1 ，但应该是 0。这是因为在补码中 -1 = 1111 1111 …. 1111，-1+1 = 1 0000 0000 …. 0000 ，由于超过了32位的比特位，所以会被截断，高位进位无效，此时等于 0000 0000 …. 0000，即为0，而且正好每一位都与 -1的每一位互补。故需要我们来对 -1 进行特判。可以在 x+1 后对其进行 !! 操作来区别最大值和 -1 。

故最终解决方法如下。

/*
 * isTmax - returns 1 if x is the maximum, two's complement number,
 *     and 0 otherwise 
 *   Legal ops: ! ~ & ^ | +
 *   Max ops: 10
 *   Rating: 1
 */
int isTmax(int x) {
  return !(~(x+1)^x)&!!(x+1);
}

4.allOddBits

该题的意思和上题差不多，就是判断 x 补码的奇数位是否全为 1，如果是就返回1，不是则返回0。并且告知了你32位是从第0位到第31位，所以不要判断错了。

读懂题意，就能想到用奇数位上全是1，偶数位上全为0的数，即0xAAAAAAAA与 x 进行与运算（&），再看其结果是否任然等于0xAAAAAAAA，若相等，则 x 符合条件，返回1，不等则返回0。同样这一题与上一题一样，无法使用等号，所以继续使用异或来判断。但是需要注意本实验有一个要求

/*
Integer constants 0 through 255 (0xFF), inclusive. You are
      not allowed to use big constants such as 0xffffffff.
*/

故无法直接定义 0xAAAAAAAA这么大的数，所以需要先得到0xAAAAAAAA。可以考虑用0xAA，通过移位和运算获得。之后就迎刃而解了。

/* 
 * allOddBits - return 1 if all odd-numbered bits in word set to 1
 *   where bits are numbered from 0 (least significant) to 31 (most significant)
 *   Examples allOddBits(0xFFFFFFFD) = 0, allOddBits(0xAAAAAAAA) = 1
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 2
 */
int allOddBits(int x) {
  int temp = 0xAA;
  int a = temp + (temp<<8);
  int b = a + (a<<16);
  return !((x&b)^b);
}

5.negate

这一题就是求 x 的相反数，一个很基础的结论就是~x + x = -1，调整一下就是 -x = ~x+1（牢记），补码的常见操作。

于是这题就解决了

/* 
 * negate - return -x 
 *   Example: negate(1) = -1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 5
 *   Rating: 2
 */
int negate(int x) {
  return ~x+1;
}

6.isAsciiDigit

该题就是来判断 x 是否在 0x30 到 0x39 之间，如果是则返回 1。

思路就是先通过右移来判断除了后4位外，其余的位是否与0x3相同，将其作为第一个条件，然后来判断后四位是否在0到9之间。

第一个条件可以通过将 x 右移4位后与0x3进行异或来判断是否相同，第二条件就将 x 和0xF进行与运算这样就可以获得后四位所表示的数了，在将其减去10，即0xA，最后只用判断减去10后的结果的符号。由于无法使用减法，所以这里使用上一题的结论，加上-10就行，（-10 = ~10+1）。

最后可以通过右移31位获得结果的符号，若为负，则为-1，若为正，则为0，又因为任何一个数与-1进行与运算都会等于自己，所以第一个条件与第二个条件均成立时才会返回 1。

/* 
 * isAsciiDigit - return 1 if 0x30 <= x <= 0x39 (ASCII codes for characters '0' to '9')
 *   Example: isAsciiDigit(0x35) = 1.
 *            isAsciiDigit(0x3a) = 0.
 *            isAsciiDigit(0x05) = 0.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 15
 *   Rating: 3
 */
int isAsciiDigit(int x) {
  int a = !((x>>4)^0x3);
  int b = ((x & 0xf) + ~0xA+1)>>31;
  return a & b;
}

7.conditional

这一题就是使用允许的运算操作符：! ~ & ^ | + << >>，来实现三目运算符，即当 x 为真时（x ≠ 0）返回 y ，为假时（x = 0），返回 z 。

首先可以先判断 x 为真为假，对 x 使用两次 ! 运算，若 x 为真，则此时为 1，反之，此时为 0。接着可以想到题目不是返回 y 就是返回 z ，所以可以想到使用或运算（|），现在需要我们在 x 为真时，将包含 z 的那一部分变为0，包含 y 的那一部分变为 y ，反之同理。然后可以想到任何一个数与 0 进行与运算都等于 0 ，任何一个数与 -1 进行与运算都等于自己本身。并且 ~0 = -1，~(-1) = 0，对于0 和 -1 都是 x 为假为真时进行取反操作可以得到的，故可以列出下表

x	a=!!x	b=~a+1	b&y	~b&z	（b&y)$\vert$(~b&z)
真	1	-1	y	0	y
假	0	0	0	z	z

可以发现完全符合题目所需，故解决方法如下

/* 
 * conditional - same as x ? y : z 
 *   Example: conditional(2,4,5) = 4
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 16
 *   Rating: 3
 */
int conditional(int x, int y, int z) {
  int a = !!x;
  int b = ~a+1;
  return (b & y)|(~b & z);
}

8.isLessOrEqual

通过题目的描述，需要我们来判断 x 与 y 的大小，如果 x <= y 时返回1，否则返回0。

首先可以很快想到如果 x 是个负数， y 是个正数，那么 x 一定小于 y，则一定返回1，相反，当 x 为正，y为负，则一定返回0。所以可以先判断符号，通过右移31来获取符号位，但由于负数一般采用的是算术右移，所以最后都需要与1进行与运算，得到符号位。

接着使用异或来判断是否符号相同，若相同，则需要用 x 减去 y，即加上-y ，再来判断相减之后的符号位，但同时要注意到当x = y时，相减之后符号位为 0 ，与 x < y时相减后情况不同，所以在此用了另一种方法，x <= y等同于 x < y+1，于是最后变为 x - y -1< 0，同时 -y = ~y +1，所以最后求的就是 x + ~y 的符号了。

/* 
 * isLessOrEqual - if x <= y  then return 1, else return 0 
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 24
 *   Rating: 3
 */
int isLessOrEqual(int x, int y) {
  int a = (x>>31)&1;
  int b = (y>>31)&1;
  int diff = a & (!b);//不同符号时,仅x为负，为y为正时，为1
  int same = a ^ b;
  int temp = ((!same) & (((x+~y)>>31)&1));
  return diff | temp;
}

9.logicalNeg

这里要求我们通过使用允许的运算操作符：~ & ^ | + << >> 来实现逻辑非操作（!），即对于 x ，只要 x 不为0 ，那么就返回 0，否则返回 1。

首先，需要知道一个不为0的数与自己的相反数进行或运算会等于一个负数，0与自己的相反数进行或运算结果还是 0 ，并且一个负数右移31位后结果为 -1 ，而 0右移31位后则还是 0，最后再加上一个1，那么就都符合题目的需求了。

/* 
 * logicalNeg - implement the ! operator, using all of 
 *              the legal operators except !
 *   Examples: logicalNeg(3) = 0, logicalNeg(0) = 1
 *   Legal ops: ~ & ^ | + << >>
 *   Max ops: 12
 *   Rating: 4 
 */
int logicalNeg(int x) {
  int a = ~x+1;
  return ((x|a)>>31)+1;
}

10.howManyBits

首先理解题意，要求求一个值使用补码来表示最少需要多少位。

通过对样例的分析可以得出结论，当 x 为正数时，在补码中位于最高位 1 之前的 0 是可以省略的，所以最少位数等于最高位 1 的位数加上 1 位符号位，而当 x 是一个负数时，同样的道理，位于最高位 0 之前的 1 也是可以省略的，所以此时最少位数等于最高位 0 的位数加上 1 位符号位，而对于 0 ，由于其补码没有符号位，所以表示只需 1 位。

按照上述过程，需要进行查找。为了方便统一，这里先将为负数的 x 取反，这样就和正数一样，只需找到最高位 1 后再加 1 位就行了，所以有如下操作

int sign = x>>31;//先取符号位。
x = ((~sign) & x) | (sign & (~x));//x为非负数则不变，x为负数则按位取反。

接下来就是进行查找了，这里可以使用到二分的思想来进行查找，先看 x 最高的 16 位，将 x 进行右移 16 位，再将其规格化。

如果最高 16 位有 1 ，那么处理后的 x 就等于 1，故此时需要的位数至少为 16位，可以对该权值进行记录，只需要将处理后的 x 左移 4位，之后就对 x 右移 16 位后的低16位（注：此时的低16位就是原本 x 的高 16位）进行二分，将低 16 位中的高 8 位进行同样的操作，从而找到在 x 高16位中最高位 1。

如果没有 1 ，那么 x 处理后就等于 0 ，记录的值也等于 0 ，此时就不需要右移，而是在 x 的低 16 位中的高 8 位进行同样的操作。

综上，x 的右移操作可以总结为 x >> 本次记录的权值。以此类推，分别对高 8 位，4 位，2 位，1位进行同样操作。最后将所有权值进行相加，不要忘了在加一个 1 （对于非 0 数是加上 1 位的符号位，对于 0 是自己本身的 1 位。），此时就满足题目的要求了。

/* howManyBits - return the minimum number of bits required to represent x in
 *             two's complement
 *  Examples: howManyBits(12) = 5
 *            howManyBits(298) = 10
 *            howManyBits(-5) = 4
 *            howManyBits(0)  = 1
 *            howManyBits(-1) = 1
 *            howManyBits(0x80000000) = 32
 *  Legal ops: ! ~ & ^ | + << >>
 *  Max ops: 90
 *  Rating: 4
 */
int howManyBits(int x) {
  int sign = x>>31;
  x = ((~sign) & x) | (sign & (~x));
  int bit_16 = (!!(x>>16))<<4;
  x = x >> bit_16;
  int bit_8 = (!!(x>>8))<<3;
  x = x >> bit_8;
  int bit_4 = (!!(x>>4))<<2;
  x = x >> bit_4;
  int bit_2 = (!!(x>>2))<<1;
  x = x >> bit_2;
  int bit_1 = (!!(x>>1));
  x = x>>bit_1;
  int bit_0 = x;
  int ans = bit_16+bit_8+bit_4+bit_2+bit_1+bit_0+1;
  return ans;
}

11.floatScale2

从这里开始就属于浮点数运算部分，首先得了解一下IEEE浮点表示，在IEEE浮点标准中用

$V=(-1)^{s} \times M\times 2^{E}$

来表示一个数。其中符号 s 表示正负（s=0表示正数，s=1表示负数），尾数M 是一个二进制小数，阶码 E 是对浮点数的加权，权重为 2 的 E 次幂（可能为负数）。因此将浮点数的位表示划分为三个部分。

一个单独的符号位 s 直接编码符号 s 。（此 s 非彼 s）

k 位的阶码字段exp 来编码阶码 E。

n 位小数字段 frac 编码位数 M ，但是编码出来的值也依赖阶码字段的值是否等于 0 。

根据 exp 的值，被编码的值可以分成三种情况，最后一种情况有两个变种。

其中小数字段 frac 被解释为描述小数值 f ，0 ≤ f <1 ，用二进制表示为

$f = 0.f_{n-1}...f_{1}f_{0}$

当 exp 的位模式既不全为 0，又不全为 1 时，则属于规格化的值，总结如下

$Bias=2^{k-1}-1$ $E=e-Bias$ $M=1+f$

当 exp 全为 0 时，则属于非规格的值，总结如下

$Bias=2^{k-1}-1$ $E=1-Bias$ $M=f$

当 exp 全为 1 时，属于特殊值，其中当小数域全为 0 时，表示的是无穷（∞），按照 s 的正负分为 +∞ 与 -∞ ；当小数域不为 0 时，结果被称为“NaN”，即不是一个数。

现在可以来看这一题了，题目需要我们求出浮点数* 2 之后的值。

首先依据IEEE浮点数分别求出单精度浮点数的符号位、阶码位以及小数位。由上面可知 float 是32位，一般 s 为 1 位，exp 为 8 位，frac 为 23 位。可以通过位运算来获得，如下

unsigned s = (uf>>31)&1;
unsigned e = (uf & 0x7f800000)>>23;
unsigned f = (uf & 0x7fffff);

然后根据上面的三种情况进行分析，即规格化的值、非规格化的值以及特殊值。其中，当为特殊值时，两种情况都是可以直接返回的。当为非规格化的值时，那么值就为 0 或无穷小，直接 2返回就行，f 此时就是尾码，所以就直接 f <<= 1。当为规格化的值时，由IEEE浮点表达式可知，只需要将exp+1，那么E也会 + 1，最终就会实现2的效果。

所以最终解决方法如下

/* 
 * floatScale2 - Return bit-level equivalent of expression 2*f for
 *   floating point argument f.
 *   Both the argument and result are passed as unsigned int's, but
 *   they are to be interpreted as the bit-level representation of
 *   single-precision floating point values.
 *   When argument is NaN, return argument
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
unsigned floatScale2(unsigned uf) {
  unsigned s = (uf>>31)&1;
  unsigned e = (uf & 0x7f800000)>>23;
  unsigned f = (uf & 0x7fffff);
  unsigned ans;

  //特殊值，直接返回
  if(e == 0xff){
      return uf;
  }else if(e == 0){//非规格化
      f <<= 1;
      ans = (s<<31)|(e<<23)|f;
  }else{//规格化
      e++;
      ans = (s<<31)|(e<<23)|f;
  }
  return ans;
  
}

12.floatFloat2Int

这个函数让我们把一个给定的浮点数 uf 转换为 int 类型。因为 int 类型的范围相较于 float 小，所以会出现精度损失的情况。

首先还是和上一题一样，求出符号位 s ，阶吗 exp ，尾数 frac。再计算一下真实的阶数 E = exp - 127。如果 E >=31 时，即为特殊值时，按照题目的要求返回 0x80000000u。如果 E < 0 时，即为非规格化的值时，此时 0<= f < 1，直接返回 0 。最后对于规格化的值，就按照正常处理，即

$V=(-1)^{s} \times M\times 2^{E}$

先算出真实的尾数 M = frac | (1 << 23)，同时 frac为23位，所以如果 E >= 23则进行加权时，则要在frac的末尾加上（E - 23）个 0，若 E < 23，则frac 末尾的（23-E）个数就无法保留，通过位运算可以实现。

同时还有一点需要注意，就是输入的数可能为负数，所以最后还需根据 s 的值进行判断。

最终代码如下

/* 
 * floatFloat2Int - Return bit-level equivalent of expression (int) f
 *   for floating point argument f.
 *   Argument is passed as unsigned int, but
 *   it is to be interpreted as the bit-level representation of a
 *   single-precision floating point value.
 *   Anything out of range (including NaN and infinity) should return
 *   0x80000000u.
 *   Legal ops: Any integer/unsigned operations incl. ||, &&. also if, while
 *   Max ops: 30
 *   Rating: 4
 */
int floatFloat2Int(unsigned uf) {
  //同样先获得符号s，尾数f，阶码e
  unsigned s = (uf>>31)&0x1;
  unsigned e = (uf>>23)&0xff;
  unsigned f = uf & 0x7fffff;
  
  int E = e - 127;
  if(E<0)return 0;
  else if(E >= 31)return 0x80000000u;
  else{
      f = f | 1<<23; 
      if(E<23){
           f >>= (23-E);
      }else{
           f <<= (E-23);
      }
  }
  if (s)return -f;
  else return f;
}

13.floatPower2

这一题要求计算浮点数2.0^x。因为在浮点数中阶码表示的意义正好就是2的多少次幂，所以我们想到对阶码出手。

但是需要先导出浮点数规格化和非规格化分别表示的浮点数的范围。

对于非规格化的 E = 1-Bias = 1- 127 = -126，而M的最小值则为0.000…1，等于 $2^{-23}$，所以非规格化浮点的最小值为 2 的 -149 次方，M的最大值则等于 $1-2^{-23}$，所以非规格化的浮点最大为 $2^{-126}\times(1-2^{-23})$。

对于规格化的浮点，M的最小值为 1 ，E 的最小值为 1- 127 = -126，所以最小为 $2^{-126}$ 。M 的最大值为 1.111…11，E 的最大值为 127，故规格化的浮点最大值不到 $2^{128}$。

就可以得到下表

格式	最小值	最大值
规格化	$2^{-126}$	$2^{127}\times(2-2^{-23})$
非规格化	$2^{-149}$	$2^{-126}\times(1-2^{-23})$

所以

x > 127时，返回NaN 。
x <= -149时，返回 0。
-126 <= x <= 127时，为规格化的，就直接让尾码全为0，控制阶码就可以了，由 x = expr - bias 可得 exp = x+ 127 。

-149 < x < -126时，为非规格化的，阶码值 E = 1 - bias = -126。这个时候只能通过控制尾码来计算。由

$M\times2^{-126}=2^{x}$

可以推断出 $M=2^{x+126}$ 。尾码的值是二次幂的形式，所以可以通过一个“1”左移获得，就可以设 1 左移了 n 位，则 $x+126 = -(23-n)$，等到n = x+ 149。

故最终解决方法如下

/* 
      * floatPower2 - Return bit-level equivalent of the expression 2.0^x
      *   (2.0 raised to the power x) for any 32-bit integer x.
      *
      *   The unsigned value that is returned should have the identical bit
      *   representation as the single-precision floating-point number 2.0^x.
      *   If the result is too small to be represented as a denorm, return
      *   0. If too large, return +INF.
      * 
      *   Legal ops: Any integer/unsigned operations incl. ||, &&. Also if, while 
      *   Max ops: 30 
      *   Rating: 4
      */
     unsigned floatPower2(int x) {
         if(x < -149)return 0;
         else if(x <= -126)return 1<<(x+149);
         else if(x <= 127)return (x+127) << 23;
         else return 0xff << 23;
     }

总结:

以上就是CSAPP DataLab的全部内容了，做完这个实验也算是对之前一段时间学习的一个巩固和练习吧，对于逻辑门运算和浮点运算也有了更多的了解。