[CSAPP]Data Lab - CedricXu

本系列文章主要用于记录我完成 CS的实验的过程和思考

实验名称：DataLab
开始时间：24/10/2023
关键词：简单逻辑二进制补码浮点数
实验内容：在只能使用一部分位运算符的情况下实现按要求对数据进行处理，共有分值不等的 13 小题，难度递增

01 bitXor#

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

要求：只能使用～和 & 运算符实现异或

分析：异或的逻辑表达式为 $F = \bar x \cdot y + x \cdot \bar y$，可以使用摩根定理将其转化为只有～和 & 的情况，但我们试试把异或看作同或的反然后使用摩根定理会怎样呢： $F = \overline{x \cdot y + \bar x \cdot \bar y} = \overline{x \cdot y} \cdot \overline{\bar x \cdot \bar y}$
我们发现这样可以节约一个操作符！

解法：

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

02 tmin#

/*
 * tmin - return minimum two's complement integer
 *   Legal ops: ! ~ & ^ | + << >>
 *   Max ops: 4
 *   Rating: 1
 */
 ```
要求：返回最小的二进制补码表示的数

分析：二进制补码表达式$$B2T_w(\vec x)=-x_{w-1}2^{w-1}+\sum^{w-2}_{i=0}x_i2^i$$
符号位为1其余为为0时取到最小值$-2^{w-1}$

解法：
```c
int tmin(void) {
  return 0x1 << 31;//将1左移31位至符号位上
}

03 isTmax#

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

要求：判断输入 x 是否为最大的二进制补码表示的数
分析：由上一题可知最大的二进制补码数为 0x7FFFFFFF，即除第一位为 0 外，其余均为 1，可以想办法把 x 化为全为 0，然后使用逻辑非 (!) 来判断

int i = x + 1; //0111...111->1000...000(i)
x += i;        //0111...111->1111...111(x)
x = ~x;        //1111...111->0000...000(x)

但是我们仔细考虑一下 x 为 - 1 (0xFFFFFFFF) 时也可以得到全零的结果，此时 i 为全零，为了消除这样的漏洞，我们可以在加上一个 i 非

i = !i;//x=Tmax -> !i=0; x=-1 -> !i=1
x += i;

解法：

int isTmax(int x) {
  int i = x + 1;
  x += i;
  x = ~x;
  i = !i;
  x += i;
  return !x;
}

04 allOddBits#

/*
 * 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
 */

要求：判断奇数位上是否都是 1 (最右边是第 0 位)

分析：这个不难，只要把偶数位都先变成 0 然后判断是不是奇数位都是 1 偶数位都是 0 (1010...1010) 就行了

解法：

int allOddBits(int x) {
  int mask = (0xAA << 8) | 0xAA;
  mask = (mask << 16) | mask;//生成1010...1010
  return !((x & mask) ^ mask);//使用异或判断是否相等
}

05 negate#

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

要求：返回相反数

分析：根据补码的定义可得 $x + ~x = -1$，则 $-x = ~x + 1$

解法：

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

06 isAsciiDigit#

/*
 * 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
 */

要求：判断是否为 Ascii 码数字，即 $0x30 \leq x \leq 0x39$

分析：从这里开始卡住了，想了很久最后还是在网上参考了解法，实在是很妙。设置两个数LowerBound(负数) 和UpperBound(正数)

若 $x \geq 0x30$，LowerBound加上 x 可以由负变正，否则仍为负数
若 $x \leq 0x39$，UpperBound加上变为负数 (溢出)，否则会变为负数
只需判断最后两个数是不是都为正数即可

解法：

int isAsciiDigit(int x) {
  int sign = 0x1 << 31;
  int LowerBound = ~0x30;
  int UpperBound = ~(sign | 0x39);//想一想为什么？
  LowerBound = sign & (LowerBound + x + 1);//加0x30仍为负故再加一
  UpperBound = sign & (UpperBound + x);
  return !(LowerBound | UpperBound);
}

07 conditional#

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

要求：实现 C 语言三目运算符x ? y : z

分析：先两次逻辑非把 x 转化为 0 或 1，如果 x 为 1 则输出 y，否则输出 z，写成逻辑表达式就好了

解法：

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

08 isLessOrEqual#

/*
 * isLessOrEqual - if x <= y  then return 1, else return 0
 *   Example: isLessOrEqual(4,5) = 1.
 *   Legal ops: ! ~ & ^ | + << >> 不能用减号！
 *   Max ops: 24
 *   Rating: 3
 */

要求：判断 x 是否小于等于 y

分析：

如果 x、y 异号，则 x 为负数时一定小于等于 y
如果 x、y 同号，则若 $y - x$ 大于 0，则 x 小于等于 y。
为什么我们不能直接判断 $y - x$，还要分两种情况呢？因为当 y 大于零，x 小于零时两个正数相加可能会溢出为负数

解法：

int isLessOrEqual(int x, int y) {
  int negX = ~x + 1;//-x
  int YminusX = negX + y;//y - x
  int Sign = YminusX >> 31 & 1;//y - x的符号
  //注意不要忘了&1因为补码右移补的是符号位！
  int Xsign = x >> 31 & 1;//x符号位
  int Ysign = y >> 31 & 1;//y符号位
  int bitXor = Xsign ^ Ysign;//xy符号是否相同
  return ((!bitXor) & (!Sign)) | ((bitXor) & (x >> 31));
}

09 LogicalNeg#

/*
 * 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
 */

要求：实现逻辑非 (!)

分析：直接～～！x (bushi)~~，前面用了这么多逻辑非，要怎么实现呢？我想了很久也没想出来，参考了网上的解法。可以发现除了 0 和 Tmin 的补码 (取反加 1) 为自身，其余数字的补码都是相反数，也就是有一个负数，取这两个数的符号位进行或操作得 1，同时 Tmin 也符合这个条件，所以不用分开判断

解法：

int logicalNeg(int x) {
  return ((x | (~x + 1)) >> 31) + 1;
  //这样看的话判断程序只取输出数的二进制最后一位
}

10 howManyBits#

/* 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
 */

要求：计算 x 最少可以用几位二进制补码表示

分析：我能想出来对负数取反然后寻找为 1 的最高位，最后看了参考答案，这解法怎么这么妙的！先寻找最高的 16 位中是否有 1，若有则至少需要 16 位，因为要保留低 16 位，然后判断前 8 位，前 4 位……(因为 Max op 有 90 所以多几步也无妨)

解法：

int howManyBits(int x) {
  int b16,b8,b4,b2,b1,b0;
  int sign=x>>31;
  x = (sign&~x)|(~sign&x);//如果负数则取反方便找1
  // 不断查找1
  b16 = !!(x>>16)<<4;//高16位有1则令b16=16
  x = x>>b16;//如果有，则将原数右移16位,方便查找高8位
  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;//+1，加上符号位
}

11 floatScale2#

/*
 * 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
 */

要求：把单精度浮点数乘 2

分析：如果非规格化，则左移一位且保留符号位 (利用非规格化可以平滑过渡到规格化的特性)；如果 NaN 或无穷大，输出自身；如果乘 2 溢出，返回无穷大；否则是规格化且不溢出，输出阶码加 1 后的值

解法：

unsigned floatScale2(unsigned uf) {
  int exp = (uf >> 23) & 0xff;//取阶码
  int sign = uf & (1 << 31);//取符号
  if(exp==0) return uf<<1|sign;//非规格化
  if (exp == 255) return uf;//NaN或无穷大
  exp++;//阶码加一即乘2
  if (exp == 255) return 0xff << 23 | sign;//溢出
  return (exp<<23)|(uf & ~(0xff << 23));//不溢出
}

12 floatFloat2Int#

/*
 * 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 类型

分析：要写一个强制类型转换啦！只要分清楚情况其实就没问题。仔细思考发现只有规格化且阶码大于等于 0 且小于等于 31 时才有意义，NaN 和正无穷自然是不行的，非规格化很小之间转化为 0，规格化且阶码小于 0 时这个数比 1 小，输出 0，规格化且阶码大于 31 时转化为 int 类型会溢出，因为阶码的大小就是左移的位数，而 int 类型只有 32 位，最后根据符号判断是否溢出

解法：

int floatFloat2Int(unsigned uf) {
  int exp = ((uf & 0x7f800000) >> 23) - 127;
  int frac = (uf & 0x007fffff) | (0x1 << 23); //第24位加1，即M = f + 1
  int sign = uf >> 31;
  
  if (exp > 31) return 0x80000000;
  if (exp < 0) return 0;//非规格化使用该算法阶码为-127符合此条件

  if (exp > 23) frac <<= (exp - 23);
  else frac >>= (23 - exp);//尾数所处的地方已经相当于向左移动23位了

  if (!((frac >> 31) ^ sign)) return frac;//如果符号没变直接输出
  else if (!sign) return 0x80000000;//若由正变负说明溢出了(但测试用例中似乎没有考察Tmin)
  else return ~frac + 1;//由负变正则输出相反数
}

13 floatPower2#

/*
 * 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
 */

要求：计算 2^x，以浮点数表示

分析：分类讨论

若 $x \leq -150$，小到无法表示为非规格化的值，输出 0
若 $-149 \leq x \leq -127$ ，可以表示为非规格化的值
若 $-126 \leq x \leq 127$，可以表示为规格化的值
若 $x \geq 128$，为 NaN 或无穷大，输出 INF

解法：

unsigned floatPower2(int x) {
  int INF = 0xff << 23;
  int exp = x + 127;//加127方便后面计算

  if (exp <= 23) return (exp << 23) | (1 << (23 - exp - 1));
  if (exp <= 0) return 0;
  if (exp >= 255) return INF;
  return exp << 23;
}

总结：#

怎么第一个 Lab 就这么难？很多非常妙的操作我根本想不出来，需要一定的技巧。建议在做的时候先自己思考，实在做不出来了不妨再到网上寻找答案，这样可以帮助我们更好地理解书中关于补码和浮点数的内容。同时呢也可以把自己的解题思路记录下来以便下次复习，像这样的实验我认为做一次是不够的。

活在当下！