CS:APP Data Lab

本筆記是 CSAPP 課程 Lab 的筆記，我預計會有自己解題的思路，以及其他優秀解答的題解，Lab 的資料可以從這裡取得。點選自學材料(Self-Study Handout)就可以安裝 Lab 的壓縮檔了。

背景知識

環境安裝

安裝完成後，執行命令解壓縮：

$ tar xvf datalab-handout.tar

可以透過 make 命令編譯 bits.c ，但是這邊會遇到一個問題，就是本作業都預設執行機器為 32 位元，解決方案就是執行以下命令：

$ sudo apt-get install gcc-multilib

測試程式

有兩種方式可以測試程式：

使用 dlc ，可以看到每個函式用的 operators 數量。

$ ./dlc -e bits.c

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 上就可以獲得中間兩項了。

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

後面許多操作都會用到此真值表

可以看到最小補數就是開頭為 1 剩餘為 0，因此擴展到 32 位就直接位移 31 位就可以了。

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 就可以寫成:

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:

~(a | b) = (~a) & (~b)

也就是要湊出一個原本式子的反邏輯，剛好 -1 + 1 = 0 ，因此可以多加一個條件: !(x + 1) ，變成以下形式:

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

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 ，改用位移操作來取得:

int allOddBits(int x) {
    int odd_mask = (0xAA << 24) | (0xAA << 16) | (0xAA << 8) | 0xAA;
    return !((x & odd_mask) ^ odd_mask);
}

`negate`

不用 - 實現 -x 。想法很簡單，直接做二補數操作就好。

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

`isAsciiDigit`

判斷 x 是否為 ASCII 數。

我的直覺是一個很傻的暴力法。

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)

但有兩個問題：

沒有減法
沒有 >=

第一個問題好解決，就如同 negate 函式一樣使用二補數即可。而第二個問題就比較複雜，再次觀察真值表，可以知道若數值為負的，第一位一定是 1。因此只要將減完的值 AND 上開頭是 1 剩餘為 0 的數，而這個數剛好就是 TMin，所以可以寫成以下:

int isAsciiDigit(int x) {
    int TMin = 1 << 31;
    return !((x + (~0x30 + 1)) & TMin) & !((0x39 + (~x + 1)) & TMin);
}

它其實就是等價於下面寫法:

return ((x - 0x30) >= 0 && (0x39 - x) >= 0) ? 1 : 0;

括弧真的要看清楚…

`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，就可以寫成:

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。

 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 就得到答案啦。

int logicalNeg(int x) {
    return (~((x | (~x + 1)) >> 31) >> 31) & 0x1;
}

精簡寫法

在做到x 為 0 時獲得 0，因為是算術右移，x 不等於 0 時獲得 -1 得時候其實簡單的將其加一就算出來啦。

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 位元裡每個區段的位元狀況，可以分成以下兩件事:

紀錄每個區間的數字累加
縮小 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 位。

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 如下圖所示，所以我們可以將每個部份取出。

int sign = (uf >> 31) & 0x1;
int exp = (uf >> 23) & 0xFF;

題目要求若是浮點數是

N a N

，則直接回傳原本的數值。但這邊要考慮到浮點數的幾個特殊例子

CSAPP $2.4.2 IEEE 浮點表示

因為無限大和

N a N

乘以 2 都是回傳原數，所以若 exp 全為 1 (0xFF)，就直接回傳原數。

if (exp == 0xFF) // infinite OR NaN
    return uf;

規格化 (normalized)

Exponent

$e$ : 代表數值的數字
$E$ :
$e - B i a s$
$B i a s$ :
$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 - B i a s$
$B i a s$ :
$2^{k - 1} - 1$ ，單精度是 127，倍精度是 1023

Fractional

$f$ :
$0. f_{n - 1} . . . f_{1} f_{0}$
$M$ :
$f$

Value

$V = 2^{E} \times M$

有差的地方：

$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 厲害的地方，因此我們可以寫成:

else if (exp == 0) // denormalized
    return ((uf & 0x7FFFFF) << 1) | (sign << 31);

而規格化的數字就簡單啦，只要將 exp 加一，就等於乘以 2 了，但要考慮到 exp 可能變成 0xFFFF，要回傳無限大回去，最後將加一的 exp 嵌回 uf 就完成了。

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 要減去

B i a s

，因為我們要的是真實的指數值。

int exp = ((uf >> 23) & 0xFF) - 127; // -126 ~ +127
int frac = (uf & 0x7FFFFF) | 0x00800000; // 1.xxx

特別注意到 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。

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 1 f_{n - 1} f_{n - 2} . . . f_{0}

所以現在就是要根據 exp 的大小調整小數點的位置。因為現在 frac 就是 23 為了，所以根據是否大於 23 來判斷左右移。

exp > 23: frac 左移 (exp - 23)
exp <= 23: frac 右移 (23 - exp)

最後在判斷正負號。

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 即超出範圍，根據題意回傳：

if (x > 127)
    return 0x7F800000;
else if (x < -126)
    return 0;

計算指數的數值表示為，

E

是真實的指數數字，

e

則是在二進制的數字表示方式:

E = e - B i a s

那現在要求的就是浮點數以二進制的方式表示，也就是求

e

，所以寫成:

e = E + B i a s

我們題目是要求

2^{x}

，而浮點數的計算就是

2^{E} \times M

，又現在

M

必為 1，因此

x = M

。因此只要將 x 加上 127 後再右移到 exp 的位置上就是浮點數的表示方式了。

unsigned floatPower2(int x) {
    if (x > 127)
        return 0x7F800000;
    else if (x < -126)
        return 0;

    return (x + 127) << 23;
}

CS:APP Data Lab

背景知識

環境安裝

測試程式

題目

bitXor

tmin

isTmax

修正問題

allOddBits

negate

isAsciiDigit

修正問題

conditional

isLessOrEqual

logicalNeg

精簡寫法

howManyBits

floatScale2

規格化 (normalized)

Exponent

Fractional

Value

非規格化 (denormalized)

Exponent

Fractional

Value

floatFloat2Int

floatPower2

Read more

Linux 核心專題: Linux 的 Preempt-RT 機制

指標篇 筆記

CS:APP Malloc Lab

DWT(5, 3) 期末專案

`bitXor`

`tmin`

`isTmax`

`allOddBits`

`negate`

`isAsciiDigit`

`conditional`

`isLessOrEqual`

`logicalNeg`

`howManyBits`

`floatScale2`

`floatFloat2Int`

`floatPower2`

指標篇筆記