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

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

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 位。

3. 依此類推：

• 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;

  
  
  
  if (exp == 0xFF) {
    return uf;
  }

  
  
  if (exp == 0) {
    
    ff <<= 1;
    
    
    
    
    if (ff > 0x7fffff) {
      ff -= 0x800000; 
      exp += 1;       
    }
  } 
  
  else {
    
    exp += 1;
    
    
    
    if (exp == 0xFF) {
      ff = 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;

  
  
  if (exp == 0xFF) {
    return 0x80000000u;
  }

  
  
  if (exp == 0) {
    return 0;
  }

  
  
  int E = (int)exp - 127;

  
  
  
  if (E < 0) return 0;

  
  
  
  ff = ff | (1 << 23);

  
  
  
  
  
  if (E >= 31) {
    return 0x80000000u;
  }

  
  
  
  
  if (E < 23) {
    
    
    
    
    ff = ff >> (23 - E);
  } else {
    
    
    
    
    ff = ff << (E - 23);
  }

  
  
  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) {
    
    
    
    
    if (x < -149)
        return 0;

    
    
    
    
    
    
    
    
    
    else if (x < -126)
        return 1 << (x + 149);

    
    
    
    
    
    
    
    
    else if (x <= 127)
        return (x + 127) << 23;

    
    
    
    
    
    else
        return (0xFF) << 23;
}

小結

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

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