owned this note
owned this note
Published
Linked with GitHub
# CS:APP Data Lab
本筆記是 CSAPP 課程 Lab 的筆記，我預計會有自己解題的思路，以及其他優秀解答的題解，Lab 的資料可以從[這裡](https://hansimov.gitbook.io/csapp/labs/labs-overview)取得。點選自學材料(Self-Study Handout)就可以安裝 Lab 的壓縮檔了。
## 背景知識
### 環境安裝
安裝完成後，執行命令解壓縮：
```
$ tar xvf datalab-handout.tar
```
可以透過 `make` 命令編譯 `bits.c` ，但是這邊會遇到一個問題，就是本作業都預設執行機器為 32 位元，解決方案就是執行以下命令：
```
$ sudo apt-get install gcc-multilib
```
### 測試程式
有兩種方式可以測試程式：
1. 使用 `dlc` ，可以看到每個函式用的 operators 數量。
```
$ ./dlc -e bits.c
```
2. `make` 編譯成功後，執行 `./btest` ，便可以看到分數以及錯誤了。
```
$ ./btest
```
### 題目
| 函式 | 說明 | 難度 | 指令數量 |
| ---------------------------------- | -------------------------- | ---- | -------- |
| `bitXor(int x,int y)` | 只用 `&` 和 `~` 實現 `x^y` | 1 | 14 |
| `tmin(void)` | 回傳最小補數 | 1 | 4 |
| `isTmax(int x)` | 判斷 `x` 是否為補數最大值 | 1 | 10 |
| `allOddBits(int x)` | 判斷是否所有奇數位元都為 1 | 2 | 12 |
| `negate(int x)` | 不用 `-` 實現 `-x` | 2 | 5 |
| `isAsciiDigit(int x)` | 判斷 `x` 是否為 ASCII 數 | 3 | 15 |
| `conditional(int x, int y, int z)` | 實現 `x ? y : z` | 3 | 16 |
| `isLessOrEqual(int x, int y)` | 實現 `x <= y` | 3 | 24 |
| `logicalNeg(int x)` | 不用 `!` 實現 `!x` | 4 | 12 |
| `howManyBits(int x)` | 計算表達 `x` 最少位元數 | 4 | 90 |
| `floatScale2(unsigned uf)` | 計算 `2.0 * uf` | 4 | 30 |
| `floatFloat2Int(unsigned uf)` | 計算 `(int) f` | 4 | 30 |
| `floatPower2(int x) ` | 計算 $2.0^x$ | 4 | 30 |
## `bitXor`
只用 `&` 和 `~` 實現 `x^y` 。這題就是大一邏輯設計的題目，我是從真值表中慢慢推出來。
| x | y | x^y |
| -------- | -------- | -------- |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以發現只有中間為是 1，所以先用 `~(x & y)` 將前三項取出。再用 ` ~(~x & ~y)` 將後三項取出。最後將其 AND 上就可以獲得中間兩項了。
```cpp
int bitXor(int x, int y) {
return (~(x & y) & ~(~x & ~y));
}
```
## `tmin`
回傳最小補數。知道二補數的數值範圍為以下，以 3 位元為例：
| 十進制 | 二補數 |
| -------- | -------- |
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| **3** | **011** |
| **-4** | **100** |
| -3 | 101 |
| -2 | 110 |
| -1 | 111 |
:::success
後面許多操作都會用到此真值表
:::
可以看到最小補數就是開頭為 1 剩餘為 0，因此擴展到 32 位就直接位移 31 位就可以了。
```cpp
int tmin(void) {
return 1 << 31;
}
```
## `isTmax`
判斷 `x` 是否為補數最大值。同樣可以看上面表格知道 TMax 是開頭為 0 剩餘的都為 1。接著要考慮的是要如何判斷是否為 TMax。我觀察到
```
TMin: 100
TMax: 011
```
若是這兩個數字做 XOR 就可以得到一個全是 1 的數字。本來想嘗試用邏輯反將其轉成0,1，但其他數仍然有可能會有位元是 1 情況。
再次觀察，若是將相同數字做 XOR ，必定會得到全是 0 的數字。
```
TMax: 011
TMax: 011
----------
XOR : 000
```
因此利用 TMin 取反得到 TMax，將其和 `x` 做 XOR 後取 `!` ，這樣就只有 TMax 才會得到 1。
### 修正問題
沒看到題目有提到不能使用 `<<` 位移操作。本來還想要想辦法湊出 TMin，可是想不出來，因此參考別人的解法。
繼續看真值表，可以看出 `TMax + 1 = TMin` 。又發現以下特性，當 TMax 和 TMin 相加會得到全是 1，也就是 -1。
```
TMax: 011
+ TMin: 100
------------
111 = -1
```
因此若是 `x` 是 TMax 時，可以是 `!(~(TMin + TMax)) = 1` 就可以寫成:
```cpp
int isTmax(int x) {
return !(~((x + 1) + x));
// return !(~(1 << 31) ^ x); // can't use << operator
}
```
但是執行後會發現錯誤:
```
ERROR: Test isTmax(-1[0xffffffff]) failed...
```
這代表帶入 `-1` 時會發生錯誤，我們拆解一下程式:
```
x = -1 (111)
(-1 + 1) + (-1) = -1
~(-1) = 0
!(0) = 1
---------------------
x = 3 (011) (TMax)
(011 + 001) + (011) = 111 = -1
~(-1) = 0
!(0) = 1
```
會發現原來 `x` 等於 TMax 和 `-1` 時會是一樣的結果，代表 `-1` 是一個特例。但我們不能使用分支。所以要利用 De Morgan's laws:
```cpp
~(a | b) = (~a) & (~b)
```
也就是要湊出一個原本式子的反邏輯，剛好 `-1 + 1 = 0` ，因此可以多加一個條件: `!(x + 1)` ，變成以下形式:
```cpp
int isTmax(int x) {
// return !(~(1 << 31) ^ x); // can't use << operator
// return !(~((x + 1) + x)); // There is a special case of "-1"
return !(~((x + 1) + x) | !(x + 1));
}
```
## `allOddBits`
判斷是否所有奇數位元都為 1，這部份我把它想的太複雜了，我以為是要從 MSB 開始算，但其實是 32 位元內的奇數位元都為 1 就好了。
如下表所示，可以將 `x` 和 `0xAAAAAAAA` 利用 AND 運算將奇數位取出來，若所有奇數位元都為 1 的數值一定會獲得 `0xAAAAAAAA` ，再來就和上題一樣利用 XOR 把同樣的值取出即可。
| x | x & 1010 | (x & 1010) ^ 1010|
| -------- | -------- | -------- |
| 0000 | 0000 | 1010
| 0001 | 0000 | 1010
| 0010 | 0010 | 1000
| 0011 | 0010 | 1000
| 0100 | 0000 | 1010
| 0101 | 0000 | 1010
| 0110 | 0010 | 1000
| 0111 | 0010 | 1000
| 1000 | 1000 | 0010
| 1001 | 1000 | 0010
| **1010** | **1010** | **0000**
| **1011** | **1010** | **0000**
| 1100 | 1000 | 0010
| 1101 | 1000 | 0010
| **1110** | **1010** | **0000**
| **1111** | **1010** | **0000**
```cpp
int allOddBits(int x) {
return !((x & 0xAAAAAAAA) ^ 0xAAAAAAAA);
}
```
> 1.Integer constants 0 through 255 (0xFF), inclusive. You are
not allowed to use big constants such as 0xffffffff.
從這裡得知不能直接使用 `0xAAAAAAAA` ，改用位移操作來取得:
```cpp
int allOddBits(int x) {
int odd_mask = (0xAA << 24) | (0xAA << 16) | (0xAA << 8) | 0xAA;
return !((x & odd_mask) ^ odd_mask);
}
```
## `negate`
不用 `-` 實現 `-x` 。想法很簡單，直接做二補數操作就好。
```cpp
int negate(int x) {
return ~x + 1;
}
```
## `isAsciiDigit`
判斷 `x` 是否為 ASCII 數。
我的直覺是一個很傻的暴力法。
```cpp
int isAsciiDigit(int x) {
return (!(x ^ 0x30) | !(x ^ 0x31) | !(x ^ 0x32) | !(x ^ 0x33) | !(x ^ 0x34) | !(x ^ 0x35) | !(x ^ 0x36) | !(x ^ 0x37) | !(x ^ 0x38) | !(x ^ 0x39));
}
```
但想當然超過了它限制的運算數。
```
dlc:bits.c:204:isAsciiDigit: Warning: 29 operators exceeds max of 15
```
### 修正問題
當然我一開始也嘗試從二進制數字看出個所以來。但我看不出來。
| 二進制 | 十進制 | 十六進制 |
| -------- | -------- | -------- |
| 110000 | 48 | 0x30 |
| 111001 | 57 | 0x39 |
解題的核心思想是要在 0x30 到 0x39 之間的區間，如下式:
```
((x - 0x30) >= 0) && ((0x39 - x) >= 0)
```
但有兩個問題：
1. 沒有減法
2. 沒有 `>=`
第一個問題好解決，就如同 `negate` 函式一樣使用二補數即可。而第二個問題就比較複雜，再次觀察真值表，可以知道若數值為負的，第一位一定是 1。因此只要將減完的值 AND 上開頭是 1 剩餘為 0 的數，而這個數剛好就是 TMin，所以可以寫成以下:
```cpp
int isAsciiDigit(int x) {
int TMin = 1 << 31;
return !((x + (~0x30 + 1)) & TMin) & !((0x39 + (~x + 1)) & TMin);
}
```
它其實就是等價於下面寫法:
```cpp
return ((x - 0x30) >= 0 && (0x39 - x) >= 0) ? 1 : 0;
```
:::success
括弧真的要看清楚...
:::
## `conditional`
實現 `x ? y : z`。我第一個想法就是使用 `!!(x)` 將 `x` 轉成 0 或 1。但接下來就想不太到了。
這邊就是二補數好玩的地方，我們可以觀察 0 和 1 的二進制：
| 十進制 | 二進制 | 取二補數(十進制） | 取二補數(二進制） |
| ------ | ------ | ----------------- | ----------------- |
| 0 | 000 | 0 | **000** |
| 1 | 001 | -1 | **111** |
看到 0 取二補數還是 0，也就是全部位元都為 0; 而 1 取二補數是 -1，也就是全部位元都為 1。這樣就可以讓我們操作位元操作了。
先用剛剛的操作將 `x` 從真假的數值轉為 0 或 1。接著將其取二補數，就會變成 0 或 -1。我們知道若是現在的 `x` 是 0 的話就是要回傳 `z`; 若是現在的 `x` 是 -1 的話就是要回傳 `y`，就可以寫成:
```cpp
int conditional(int x, int y, int z) {
x = !!(x);
x = ~x + 1;
return (x & y) | (~x & z);
}
```
兩種情況就可以寫成:
```
x = 0
(000 & y) | (111 & z) = z
--------------------------
x = -1
(111 & y) | (000 & z) = y
```
## `isLessOrEqual`
實現 `x <= y` ，小於等於其實就直接做減法看是否小於 0 就好了。和 `isAsciiDigit` 函式用到的作法一模一樣，將 `y` 減去 `x` 再和 TMin 判斷是否小於 0。
```cpp
int isLessOrEqual(int x, int y) {
int TMin = 1 << 31;
return !((y + (~x + 1)) & TMin);
}
```
## ``logicalNeg``
不用 `!` 實現 `!x` 。
0 的特性就是做二補數仍然為 0，而其他非 0 數值，若是正數做二補數後第一個位元一定是 1，若是負數則本身第一個位元就是 1 了。因此我可以將 `x` 和其二補數 `~x + 1` 做 OR 運算。
* `x = 0`: 第一個位元必定是 0
* `x != 0`: 第一個位元必定是 1
為了取得第一個位元，將其右移 31 位，這樣就可以保證 `x` 為 0 時獲得 0，因為是算術右移，`x` 不等於 0 時獲得 -1。
```
(x | (~x + 1)) >> 3
------------------
x = 0
(000 | 000) = 000
000 >> 3 = 000
------------------
x = 1
(001 | 111) = 111
111 >> 3 = 111
------------------
x = -2
(110 | 010) = 110
110 >> 3 = 111
```
因為 0 和 -1 分別代表全 0 和全 1，所以先取反再右移 31
位，就可以做到顛倒了:
```
~(000) >> 3 = 111
------------------
~(111) >> 3 = 000
```
因為要回傳的值只要 0 或 1，因此最後 AND 上 `0x1` 就得到答案啦。
```cpp
int logicalNeg(int x) {
return (~((x | (~x + 1)) >> 31) >> 31) & 0x1;
}
```
### 精簡寫法
在做到`x` 為 0 時獲得 0，因為是算術右移，`x` 不等於 0 時獲得 -1 得時候其實簡單的將其加一就算出來啦。
```diff
int logicalNeg(int x) {
- // return (~((x | (~x + 1)) >> 31) >> 31) & 0x1; // its work, but too complicate
+ return ((x | (~x + 1)) >> 31) + 1;
}
```
## `howManyBits`
計算表達 `x` 最少位元數。
題目的意思是 `x` 用二補數表示需要幾個位元，例如
```
howManyBits(12) = 5 // 4位(0...1100) + 符號位
-----------------------------------------------------
howManyBits(298) = 10 // 9位(0...1,0110,1010) + 符號位
-----------------------------------------------------
howManyBits(-5) = 4 // 3位(1...010) + 符號位
-----------------------------------------------------
howManyBits(0) = 1 // (0...0) + 符號位
-----------------------------------------------------
howManyBits(-1) = 1 // (1...1) + 符號位
-----------------------------------------------------
howManyBits(0x80000000) = 32 // 32位(1000...0000)
```
所以可以看出核心思想是要用幾個位元表示，正或負其實是一樣的位元數就可以表達的，因此可以先將判斷數值正負再將其取反，而為什麼不是取二補數，以 -5 做例子，最少位數取決於最高有效位的位置，而不是實際的二補數值。
| -5 | Column 2 |
| ---------- | ----------- |
| 原始二進制 | 1111...1011 |
| ~(-5) | 0000...0100 |
| ~(-5) + 1 | 0000...0101 |
為了要取得 32 位元裡每個區段的位元狀況，可以分成以下兩件事:
1. 紀錄每個區間的數字累加
2. 縮小 `x` 的範圍
可以用二元搜尋的概念，從 16, 8, 4, 2, 1, 0 個位元判斷。以 16 位元舉例:
* `abs_x >> 16` 可以取出高 16 位
* `!!(abs_x >> 16)` 若是高 16 位有 1 為 1，反之則為 0
* `b16 = (!!(abs_x >> 16)) << 4` 若是高 16 位有 1 則 `b16` 為 16 ，反之則為 0
* `abs_x = abs_x >> b16` 將 `x` 右移 `b16` 位
最後將所有位置的變數加起來後加上符號位就是答案了。
以上面 -5 為例子，因為是負數所以取反
```
1111...1011 -> 0000...0100
```
* 右移 16 位皆為 0
* 右移 8 位皆為 0
* 右移 4 位皆為 0
* 右移 2 位不為 0 ，因此 `b2` 為 2 ，`x` 右移 2 位，變成 0000...0001
* 右移 1 位皆為 0
* `b0` 為 0000...0001
最後就是 `b2` + `b0` + 1 ，也就是 4 位。
```cpp
int howManyBits(int x) {
int sign = (x >> 31);
int abs_x = (sign & (~x)) | (~sign & x);
int b16, b8, b4, b2, b1, b0;
b16 = (!!(abs_x >> 16)) << 4;
abs_x = abs_x >> b16;
b8 = (!!(abs_x >> 8)) << 3;
abs_x = abs_x >> b8;
b4 = (!!(abs_x >> 4)) << 2;
abs_x = abs_x >> b4;
b2 = (!!(abs_x >> 2)) << 1;
abs_x = abs_x >> b2;
b1 = (!!(abs_x >> 1));
abs_x = abs_x >> b1;
b0 = abs_x;
return b16 + b8 + b4 + b2 + b1 + b0 + 1;
}
```
## `floatScale2`
計算 `2.0 * uf` 。
本題以無號數來表示單精度的浮點數，根據 IEEE 754 如下圖所示，所以我們可以將每個部份取出。
```cpp
int sign = (uf >> 31) & 0x1;
int exp = (uf >> 23) & 0xFF;
```
題目要求若是浮點數是 $NaN$ ，則直接回傳原本的數值。但這邊要考慮到浮點數的幾個特殊例子
> CSAPP $2.4.2 IEEE 浮點表示
因為無限大和 $NaN$ 乘以 2 都是回傳原數，所以若 `exp` 全為 1 (`0xFF`)，就直接回傳原數。
```cpp
if (exp == 0xFF) // infinite OR NaN
return uf;
```
### 規格化 (normalized)
#### Exponent
* $e$ : 代表數值的數字
* $E$ : $e - Bias$
* $Bias$ : $2^{k-1} - 1$ ，單精度是 127，倍精度是 1023
#### Fractional
* $f$ : $0.f_{n-1}...f_{1}f_{0}$
* $M$ : $1 + f$
#### Value
* $V = 2^{E}\times M$
---
### 非規格化 (denormalized)
#### Exponent
* $e$ : 必為 0
* $E$ : $1 - Bias$
* $Bias$ : $2^{k-1} - 1$ ，單精度是 127，倍精度是 1023
#### Fractional
* $f$ : $0.f_{n-1}...f_{1}f_{0}$
* $M$ : $f$
#### Value
* $V = 2^{E}\times M$
:::info
有差的地方：
* $E$ 的數值
* $M$ 的數值
:::
以下是課本的範例題目：
考慮到非規格化，其 `exp` 為 0，而要將其乘以 2，其實只要把 `frac` 的地方乘以 2 就好，也就是直接左移 1 位。
但思考一下，若是 `frac` 已經是全是 1，也就可能導致溢位到 `exp` 呢。我們拿個例子: `0 0000 111` 是最大的非規格化數，從上表已經算出其十進制數字為 $\frac{7}{512}$，若是直接將其 `frac` 右移 1 位就變成 `0 0001 110` ，會是 $\frac{7}{256}$ 嘛？
| Bit representation | $e$ | $E$ | $2^E$ | $f$ | $M$ | $2^E\times M$ |
| ------------------ | --- | --- | -------------- | ------------- | -------------- | --------------- |
| `0 0001 110` | 1 | -6 | $\frac{1}{64}$ | $\frac{6}{8}$ | $\frac{14}{8}$ | $\frac{7}{256}$ |
會發現竟然對上了，這也是 IEEE 754 厲害的地方，因此我們可以寫成:
```cpp
else if (exp == 0) // denormalized
return ((uf & 0x7FFFFF) << 1) | (sign << 31);
```
而規格化的數字就簡單啦，只要將 `exp` 加一，就等於乘以 2 了，但要考慮到 `exp` 可能變成 `0xFFFF`，要回傳無限大回去，最後將加一的 `exp` 嵌回 `uf` 就完成了。
```cpp
unsigned floatScale2(unsigned uf) {
int sign = (uf >> 31) & 0x1;
int exp = (uf >> 23) & 0xFF;
if (exp == 0xFF) // infinite OR NaN
return uf;
else if (exp == 0) // denormalized
return ((uf & 0x7FFFFF) << 1) | (sign << 31);
exp += 1;
if (exp == 0xFF) // overflow to infinite
return (sign << 31) | 0x7F800000;
return (uf & 0x807FFFFF) | (exp << 23); // normalized
}
```
## `floatFloat2Int`
計算 `(int) uf`。
本題要計算將浮點數轉成整數，因此可以先將 `exp` 和 `frac` 求出來，比較不一樣的是 `exp` 要減去 $Bias$ ，因為我們要的是真實的指數值。
```cpp
int exp = ((uf >> 23) & 0xFF) - 127; // -126 ~ +127
int frac = (uf & 0x7FFFFF) | 0x00800000; // 1.xxx
```
:::info
特別注意到 `frac` 比起上題多 OR 上了 `0x00800000` 。目的就是為了取出 `frac` 的更高一位，因為有一個隱含以 1 開頭的(Implied leading 1) ，把 $M$ 看成 $1.f_{n-1}f_{n-2}...f_{0}$ 。
:::
單精度的指數範圍 $-126$ ~ $127$ ，而整數的範圍只有到 $2^{31}-1$ ，所以大於 31 的數值按題意將回傳 `TMin` 。而小於 0 的數值則皆回傳 0。
```cpp
if (exp > 31)
return TMin;
else if (exp < 0)
return 0;
```
知道浮點數的答案為
$$
V = 2^{E}\times M
$$
我們剛剛已經把原本的 $M$ 表示成沒有小數點:
$$
M=1.f_{n-1}f_{n-2}...f_{0}\Rightarrow 1f_{n-1}f_{n-2}...f_{0}
$$
所以現在就是要根據 `exp` 的大小調整小數點的位置。因為現在 `frac` 就是 23 為了，所以根據是否大於 23 來判斷左右移。
* `exp > 23`: `frac` 左移 `(exp - 23)`
* `exp <= 23`: `frac` 右移 `(23 - exp)`
最後在判斷正負號。
```cpp
int floatFloat2Int(unsigned uf) {
int TMin = 1 << 31;
int exp = ((uf >> 23) & 0xFF) - 127; // -126 ~ +127
int frac = (uf & 0x7FFFFF) | 0x00800000; // 1.xxx
if (exp > 31)
return TMin;
else if (exp < 0)
return 0;
frac = (exp > 23) ? (frac << (exp - 23)) : (frac >> (23 - exp));
return (uf & TMin) ? -frac : frac;
}
```
## `floatPower2`
計算 $2.0^x$ 。
我們知道 $2.0^x$ 是一定不會有小數點的，因此 `frac` 一定皆為 0。並且一定為正，所以 `sign` 也一定為 0。
所以我們只須考慮 `exp` 。如上題所述，單精度的指數範圍 $-126$ ~ $127$ ，若指數次方大於 127 或小於 -126 即超出範圍，根據題意回傳：
```cpp
if (x > 127)
return 0x7F800000;
else if (x < -126)
return 0;
```
計算指數的數值表示為，$E$ 是真實的指數數字，$e$ 則是在二進制的數字表示方式:
$$
E = e - Bias
$$
那現在要求的就是浮點數以二進制的方式表示，也就是求 $e$ ，所以寫成:
$$
e=E+Bias
$$
我們題目是要求 $2^x$ ，而浮點數的計算就是 $2^E\times M$ ，又現在 $M$ 必為 1，因此 $x=M$ 。因此只要將 `x` 加上 127 後再右移到 `exp` 的位置上就是浮點數的表示方式了。
```cpp
unsigned floatPower2(int x) {
if (x > 127)
return 0x7F800000;
else if (x < -126)
return 0;
return (x + 127) << 23;
}
```
Google Drive
Gist
Clipboard
Sign in with Wallet
