[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 = \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 就這麼難？很多非常妙的操作我根本想不出來，需要一定的技巧。建議在做的時候先自己思考，實在做不出來了不妨再到網上尋找答案，這樣可以幫助我們更好地理解書中關於補碼和浮點數的內容。同時呢也可以把自己的解題思路記錄下來以便下次複習，像這樣的實驗我認為做一次是不夠的。

活在當下！