banner
CedricXu

CedricXu

计科学生 / 摄影爱好者

[CSAPP]データラボ

本系列文章主要用于记录我完成 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=xy+xˉyˉ=xyxˉ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 就这么难?很多非常妙的操作我根本想不出来,需要一定的技巧。建议在做的时候先自己思考,实在做不出来了不妨再到网上寻找答案,这样可以帮助我们更好地理解书中关于补码和浮点数的内容。同时呢也可以把自己的解题思路记录下来以便下次复习,像这样的实验我认为做一次是不够的。

活在当下!

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。