CSAPP Data Lab 解析

發表於 分類於 閱讀次數： Waline： 文章字數： 7.6k

前一段時間做完了 CSAPP 的第一個 Lab，寫一篇總結。（其實這篇文章拖了很久）

CS:APP Data Lab 旨在通過一系列位操作謎題，訓練對整數和浮點數底層表示（特別是補碼和 IEEE 754 標準）的理解。要求在嚴格限制的操作符和操作數數量下，實現特定的數學或邏輯功能。

函數名 (Name) 描述 (Description) 難度 (Rating) 最大操作數 (Max ops)
bitXor(x, y) 只使用 & 和 ~ 實現 x ^ y (異或)。 1 14
tmin() 返回最小的補碼整數 (Two’s complement integer)。 1 4
isTmax(x) 僅當 x 是最大的補碼整數時返回 True。 1 10
allOddBits(x) 僅當 x 的所有奇數位都為 1 時返回 True。 2 12
negate(x) 返回 -x，不使用 - 運算符。 2 5
isAsciiDigit(x) 如果 0x30 <= x <= 0x39 (即 ASCII 數字字元) 則返回 True。 3 15
conditional(x, y, z) 等同於 x ? y : z (三元運算符)。 3 16
isLessOrEqual(x, y) 如果 x <= y 返回 True，否則返回 False。 3 24
logicalNeg(x) 計算 !x (邏輯非)，不使用 ! 運算符。 4 12
howManyBits(x) 用補碼表示 x 所需的最小位數。 4 90
floatScale2(uf) 對於浮點參數 f，返回 2 * f 的位級等價表示。 4 30
floatFloat2Int(uf) 對於浮點參數 f，返回 (int)f 的位級等價表示。 4 30
floatPower2(x) 對於整數 x，返回 2.0^x 的位級等價表示。 4 30

bitXor

該題要求僅使用 ~（取反） 和 &（與），實現 ^（異或）

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

使用 De Morgan 律，容易得到 ~(x&y) = (～x)|(~y)，於是我們可以使用 ~ 和 & 實現 | 操作。

異或操作，可以表示為 x^y = (~x & y) | (x & ~y)，結合 De Morgan 律，我們很容易得到最終的答案 x^y = ~((~(x&~y))&(~((~x)&y)))。

tmin

這道題很簡單，返回最小的補碼整數。回顧補碼的定義，最高位取負權，故令符號位為 1 即可。

1
2
3
int tmin(void) {
  return 1<<31;
}

isTmax

判斷 x 是否是最大的補碼。若是，返回 1；否則，返回 0。

1
2
3
4
5
int isTmax(int x) {
  int map = x + 1;
  int res = ~(map + x);
  return !res & (!!map);
}

最大的補碼有一個性質，加一之後變成最小的補碼：0x7fffffff -> 0x80000000

而最大的補碼加上最小的補碼等於 0xffffffff 即 -1，取反之後為 0 （這裡推出 0 是為了得到返回值中的 0/1）

因此，我們可以通過 ~(x+x+1) 得到答案。

但是 -1+0 也等於 -1，即如果 x=0 時，~(x+x+1) 同樣等於 1，是一個 Corner Case。

因此，我們還需要對結果與 !!(x+1)，才能得到最終的答案。（如果 x=-1，!!(x+1)=0；其餘情況均為 1）

於是我們得到最終的答案 !(~(x+x+1)) & (!!(x+1))

allOddBits

僅當 x 的所有奇數位都為 1 時返回 1

1
2
3
4
5
6
int allOddBits(int x) {
  int a = 0xAA;
  int b = (a<<8) + (a<<16) + (a <<24) + a;
  int bm = ~b+1;
  return !((x&b)+bm);
}

我們做一個奇數位掩碼即可 0xAA = 0b10101010，通過左移，可以得到 a + (a<<8) + (a<<16) + (a <<24) = 0xAAAAAAAA = b

於是 x&b 取出所有奇數位，但是我們需要得到 0/1 的答案

bm = ~b + 1，得到 -b（取反加一是補碼相反數），b+(-b) = 0，再取邏輯非，就可以得到答案

negate

這道題要求不使用 - 運算符計算 -x

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

非常簡單，根據補碼的定義得到。取反加一就是相反數。

isAsciiDigit

如果 0x30 <= x <= 0x39 (即 ASCII 數字字元) 則返回 True。

我們在這道題中不能使用 <= 這類運算符，因此，我們想到，進行減法之後取符號位的操作。

1
2
3
4
5
int isAsciiDigit(int x) {
    int ge_30 = !((x + (~0x30 + 1)) >> 31);     
    int le_39 = !((0x39 + (~x + 1)) >> 31); 
    return ge_30 & le_39; 
}

conditional

使用位運算實現三目運算符（x ? y : z）

1
2
3
4
5
int conditional(int x, int y, int z) {
  int xb = !(!x);
  int M = ~xb + 1;
  return (M&y) | (~M&z);
}

我們可以使用邏輯掩碼

先使用 !(!x) 將 x 轉換成 0/1，記為 xb

~xb + 1，則有 0 -> 0；1 -> -1 = 0xffffffff（掩碼，取所有位）

因此，(M&y) | (~M&z) 就是最終的答案。

如果 x = 1，M = 0xffffffff，~M = 0，取 y；否則，取 z

isLessOrEqual

1
2
3
int isLessOrEqual(int x, int y) {
  return !((y+(~x+1))>>31);
}

簡單判斷符號位即可。但是實現的是 <=，對 > 取非即可

logicalNeg

計算 !x (邏輯非)，不使用 ! 運算符

1
2
3
int logicalNeg(int x) {
  return ((x>>31) | ((~x+1)>>31))+1;
}

howManyBits

計算用補碼表示 x 所需的最小位數

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int howManyBits(int x) {
  int fg = x>>31;
  x = ((~fg) & x) | (fg &(~x));
  int h16 = !!(x >> 16) << 4;
  x >>= h16;
  int h8 = !!(x>>8) << 3;
  x >>= h8;
  int h4 = !!(x>>4) << 2;
  x >>= h4;
  int h2 = !!(x>>2) << 1;
  x>>=h2;
  int h1 = !!(x>>1);
  x>>=h1;
  int h0 = x;
  return h0 + h1 + h2 + h4 + h8 + h16 + 1;
}

這道題，先選取符號位，然後計算之後的最高位即可。

為了方便計算，我們把負數補碼表示為正數，這樣就只用計算最高位的 1 在哪裡就行了

((~fg) & x) | (fg & (~x)) 是一個條件取反操作，相當於 x = (x < 0) ? ~x : x

  • 若 fg 為 0（正數）：表達式變為 (All_1 & x) | (0 & ~x) -> x。保持不變。
  • 若 fg 為 -1（負數）：表達式變為 (0 & x) | (All_1 & ~x) -> ~x。按位取反。

這裡提醒各位，此處補碼右移是算術右移，所以負數右移得到一個所有位都為 1 的數，也就是 -1。

接下來進行位的二份尋找：

這裡的邏輯是**“分治法”**。我們有 32 位要檢查，像二分尋找一樣：

  1. 檢查高 16 位：

    • x >> 16：如果不為 0，說明最高位的 1 在高 16 位中（即位 16-31）。
    • !!(...)：將結果轉化為 0 或 1。如果高 16 位有數，結果為 1，否則為 0。
    • 1<< 4：如果高 16 位有數，說明我們至少需要 16 位，即 1 << 4 = 16。
    • h16：這就是我們找到的基數（0 或 16）。
    • x >>= h16：關鍵點。如果我們確定高 16 位有數，我們將 x 右移 16 位，丟棄低 16 位，接下來的檢查只關注剛才的高 16 位。如果高 16 位全是 0，x 保持不變，我們繼續檢查原本的低 16 位。

  2. 檢查高 8 位（在剩下的 16 位範圍內）：

邏輯同上。如果剩下的這部分的高 8 位有數，則 h8 = 8，並將 x 右移 8 位。

  1. 依此類推：
  • h4：檢查剩下的 4 位中的高 2 位… (這裡代碼邏輯是一致的，檢查高4位)。
  • h2：檢查剩下的 4 位。
  • h1：檢查剩下的 2 位。
  • h0 = x：檢查最後剩下的 1 位。

最後，我們計算 h16+…+h0 的總和即可。這裡要注意，補碼有一個符號位，所以結果還要再 +1。

得到答案：h0 + h1 + h2 + h4 + h8 + h16 + 1

floatScale2

對於浮點參數 f，返回 2 * f 的位級等價表示

IEEE 754

我們先來回顧一下浮點數的位級表示，即 IEEE 754，這裡以 float 為例

浮點數位中有三段：

  • Sign (s): 1 bit [31] -> 符號位
  • Exponent (exp): 8 bits [30:23] -> 階碼
  • Fraction (frac): 23 bits [22:0] -> 尾數
1
2
3
int sign = (uf >> 31) & 0x1;
int exp  = (uf >> 23) & 0xFF;
int frac = uf & 0x7FFFFF;

對於一個浮點數的解釋，有三種情況：

Case A: 非規格化 (Denormalized)

  • 特徵：exp == 0
  • 真實值：V=(−1)s×M×21−BiasV = (-1)^s \times M \times 2^{1-Bias}
    • 這裡 M=0.fracM = 0.frac (沒有隱含的 1)

Case B: 規格化 (Normalized)

  • 特徵：exp != 0 且 exp != 255
  • 真實值：V=(−1)s×M×2exp−BiasV = (-1)^s \times M \times 2^{exp-Bias}
    • 這裡 M=1.fracM = 1.frac (有一個隱含的 1)
    • Bias = 127

Case C: 特殊值 (Special Values)

  • 特徵：exp == 255 (全 1)
  • 類型：
    • frac == 0：Infinity (無窮大)
    • frac != 0：NaN (Not a Number)

接下來我們看這道題，這道題只需要注意分類討論就可以。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
unsigned floatScale2(unsigned uf) {
  unsigned s = uf >> 31;
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned ff = uf & 0x7fffff;

  // 特殊值 (Special Values)
  // 如果階碼全為1 (exp == 255)，表示 NaN (非數) 或 Infinity (無窮大)
  // 規則：NaN * 2 = NaN, Inf * 2 = Inf，直接返回原值
  if (exp == 0xFF) {
    return uf;
  }

  // 非規格化數 (Denormalized)
  // 如果階碼為0，表示非規格化數，數值非常接近 0
  if (exp == 0) {
    // 非規格化數乘以2：直接將尾數左移一位
    ff <<= 1;
    
    // 檢查尾數是否溢出 (從非規格化過渡到規格化)
    // 如果左移後 ff 超過了 23 位能表示的最大值 (即 0x7fffff)
    // 說明最高位變成了 1，這個 1 應該“進位”給階碼
    if (ff > 0x7fffff) {
      ff -= 0x800000; // 去掉溢出的那一位 (因為它現在變成了隱含的 1)
      exp += 1;       // 階碼從 0 變為 1 (成為規格化數)
    }
  } 
  // 規格化數 (Normalized)
  else {
    // 規格化數乘以2：直接給階碼加 1
    exp += 1;
    
    // 檢查階碼上溢 (Overflow)
    // 如果加 1 後階碼變成了 255，說明數值太大，變成了無窮大 (Infinity)
    if (exp == 0xFF) {
      ff = 0; // 無窮大的定義是 exp=255 且 frac=0
    }
  }

  return (s << 31) | (exp << 23) | (ff);
}```

## floatFloat2Int

對於浮點參數 `f`，返回 `(int)f` 的位級等價表示

```c
int floatFloat2Int(unsigned uf) {
  unsigned s = uf >> 31;
  unsigned exp = (uf >> 23) & 0xFF;
  unsigned ff = uf & 0x7fffff;

  // 處理特殊情況：NaN (非數) 或 Infinity (無窮大)
  // 當階碼全為 1 時。根據題目要求，越界通常返回 TMin (0x80000000)
  if (exp == 0xFF) {
    return 0x80000000u;
  }

  // 處理非規格化數 (Denormalized)
  // 當階碼全為 0 時，數值極小 (0.xxxx * 2^-126)，轉換為 int 必定為 0
  if (exp == 0) {
    return 0;
  }

  // 計算真實指數 E
  // Bias (偏置值) 是 127。 E = exp - Bias
  int E = (int)exp - 127;

  // 處理小於 1 的數
  // 如果真實指數小於 0 (例如 2^-1, 2^-2)，數值為 0.xxxx
  // 強轉 int 會向零截斷，結果為 0
  if (E < 0) return 0;

  // 還原隱含的 1 (Restore Implicit 1)
  // 規格化數的真實尾數形式是 1.fffff...
  // 我們手動把第 23 位置 1，代表那個隱含的整數部分 "1"
  ff = ff | (1 << 23);

  // 處理溢出 (Overflow)
  // 如果指數 E >= 31，說明數值 magnitude >= 2^31
  // int 的最大值是 2^31 - 1。
  // 無論是正數溢出，還是負數正好是 TMin (-2^31) 或更小，
  // 按照題目規則，都返回 TMin (0x80000000)
  if (E >= 31) {
    return 0x80000000u;
  }

  // 位移對齊 (Bit Shifting)
  // 現在的 ff 看起來是這樣： [1]. [xxxxxx]... (1 在第 23 位)
  // 這相當於 1.xxxxx * 2^23 (如果在整數暫存器看)
  // 我們實際需要的是 1.xxxxx * 2^E
  if (E < 23) {
    // 情況 A: 指數較小 (例如 E = 20)
    // 我們需要將小數點右移 20 位。
    // 但當前 ff 是左對齊在第 23 位的，所以需要**右移**丟棄多餘的小數位。
    // 移位量 = 23 - 20 = 3
    ff = ff >> (23 - E);
  } else {
    // 情況 B: 指數較大 (例如 E = 30)
    // 我們需要將小數點右移 30 位。
    // 當前只在第 23 位，不夠，需要**左移**補零。
    // 移位量 = 30 - 23 = 7
    ff = ff << (E - 23);
  }

  // 處理符號
  // 如果原數是負數，進行取反加一 (即 -ff)
  if (s) return -ff;
  
  // 原數是正數，直接返回
  return ff;
}

floatPower2

對於整數 x，返回 2.0^x 的位級等價表示。對於這道題，計算出幾個臨界點即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
unsigned floatPower2(int x) {
    // 1. 處理下溢 (Underflow)
    // 最小的非規格化數是 2^(-149)。
    // 計算邏輯：Min Denorm = 2^(1-Bias) * 2^(-23) = 2^(-126) * 2^(-23) = 2^(-149)
    // 如果 x 比這個還小，說明數值太小無法表示，直接返回 0.0
    if (x < -149)
        return 0;

    // 2. 處理非規格化數 (Denormalized)
    // 範圍：[-149, -127]
    // 非規格化數的階碼 (exp) 全為 0，值公式為：M * 2^(-126)
    // 我們需要構建 2^x。
    // 方程：2^x = (1 << shift) * 2^(-23) * 2^(-126)  <-- (1<<shift)*2^-23 是尾數部分
    //      2^x = 2^shift * 2^(-149)
    //      x = shift - 149
    //      shift = x + 149
    // 所以，我們將 1 左移 (x + 149) 位放在尾數部分 (Fraction)
    else if (x < -126)
        return 1 << (x + 149);

    // 3. 處理規格化數 (Normalized)
    // 範圍：[-126, 127]
    // 規格化數的值公式為：1.0 * 2^(exp - Bias)
    // 我們需要 2^x，尾數部分保持為 0 (即 1.0)，只需要設置階碼。
    // 方程：x = exp - Bias
    //      exp = x + Bias
    //      exp = x + 127
    // 將計算出的 exp 移到階碼的位置 (第 23-30 位)
    else if (x <= 127)
        return (x + 127) << 23;

    // 4. 處理上溢 (Overflow)
    // 範圍：x > 127
    // 單精度浮點數最大能表示的 2 的冪是 2^127。
    // 超過這個值，返回正無窮大 (+Infinity)。
    // +Inf 的表示：符號位 0，階碼全 1 (0xFF)，尾數全 0。
    else
        return (0xFF) << 23;
}

小結

Data Lab 實驗使我深入理解整數（補碼）和浮點數（IEEE 754）在二進制層面的表示方法，透過使用一組極其受限的位運算符（如 ~, &, |, ^, +, <<, >>）來實現複雜的邏輯、算術、比較和類型轉換操作，從而真正掌握了位運算的技巧。

我的代碼存放在 aeilot/CSAPP-Labs。