十進位：你早就會的「位值系統」

十進位（decimal）是日常使用的標準數字系統——恰好用了跟手指一樣多的數字！ 十進位稱為基底 10（base 10），因為它使用 10 個不同的數字（0–9）， 可用下標 10 標記，例如 \(123_{10}\)。

一個十進位數的值 = 每個數字乘上對應的 10 的冪次，再全部相加：

這個「位值」觀念你早已內化成直覺——關鍵是：基底不一定要是 10！

二進位（Binary）

二進位數的值 = 每個 1 位元所在位置對應的 2 的冪次之和。

十六進位（Hexadecimal）

十六進位最重要的用途是作為二進位的速記法： 每個十六進位數字恰好對應一個 4 位元二進位數 （因為 4 位元恰有 \(2^4 = 16\) 種可能）：

同一個值只需 \(1/4\) 的十六進位數字就能表達，讀寫都更有效率、更不易出錯。

八進位（Octal）

基底轉換（Base Conversion）

既然十六進位與八進位都只是二進位的速記， 在不同基底間轉換時，先經過二進位是最不易出錯的路徑：

不只是速記：實際應用

• 八進位——Unix 檔案權限：Linux 等類 Unix 系統以八進位顯示與設定檔案權限。 例如 chmod 754 filename：

  	user：7			group：5			other：4
  二進位	1	1	1	1	0	1	1	0	0
  權限	r	w	x	r	\(-\)	x	r	\(-\)	\(-\)

  每組 3 個位元恰好是一個八進位數字：r（讀）、w（寫）、x（執行）。

• 十六進位——記憶體位址：十六進位在計算領域無所不在， 用來把冗長的二進位變得可讀，最典型的是記憶體位址 （資料儲存位置的編號），例如 0x7ffee4a3c8b0。

基底 \(N\) 的值與範圍

同一串數字在不同基底下代表不同的值——「101」是什麼要看表示法：

範圍為什麼重要？電腦是有限的機器，每種資料型別都用固定量的記憶體儲存。 範圍告訴我們不同型別能表示的最小與最大值。 例如 unsigned int 若用 4 位元組儲存（1 位元組 byte = 8 位元）， 就能存 \(2^{4\times8} = 2^{32}\) 個值，即十進位整數 \(0\) 到 \(4{,}294{,}967{,}295\)。

數字可以是什麼？

二進位數是電腦系統的基石，但這些值可以代表任何東西： 數量、顏色（如 RGB 0xFF6600）、字元（如 ASCII 編碼 \(65 =\)「A」）、 角度……端看我們如何詮釋這串位元。 「表示法」正是第 3 章的核心——同一串位元，用不同表示法讀，值完全不同。

二進位加法（Binary Addition）

\(1 + 1\) 等於多少？

回到加法的基本功：兩個單一位元相加，可能的結果是什麼？

輸入只能是 0 或 1，但輸出有三種可能：0、1、2（\(0b00\)、\(0b01\)、\(0b10\)）—— 需要兩個位元才裝得下。 於是輸出拆成兩個單位元訊號：和（Sum, \(S\)）與進位（Carry, \(C\)）。

半加器（Half Adder）

回顧第一週的邏輯運算子——哪兩個的真值表跟 \(C\)、\(S\) 一模一樣？ \(C\) 欄是 AND、\(S\) 欄是 XOR！ \[\boxed{C = A \land B, \qquad S = A \oplus B}\]

有了這兩條式子，就能把 2 個單位元訊號相加。 但要加多位元的數，還缺一塊拼圖。

直式加法與進位

十進位與二進位的直式加法都靠進位（carry）把資訊往左傳： 從最右邊的數字（二進位是 bit 0，即 LSB）開始加， 其進位參與緊鄰左邊那一位（bit 1）的計算，依此類推。

右例：\(1001_2 + 1101_2 = 10110_2\)（\(9 + 13 = 22\) ✓）。 黃色的第 5 個位元是溢位（overflow）—— 我們目前用 4 位元表示數字，裝不下第 5 位。 暫時先忽略它，第 3 章會回來詳談！

全加器（Full Adder）

多位元加法時，每一位除了 \(A\)、\(B\) 還要吃前一位的進位—— 需要第三個輸入 \(C_{in}\)：

（檢查：三個輸入的 1 的個數 = \(2 \cdot C_{out} + S\)， 例如三個都是 1 時 \(3 = 2 \cdot 1 + 1\) ✓。）

全加器公式：Sum

把 \(S\) 填入卡諾圖（列 \(AB\)、欄 \(C_{in}\)）：

棋盤式分布——沒有任何相鄰的 1 可以圈在一起！ 用 DNF 直接寫出（這已是只用 \(\lnot, \land, \lor\) 的最簡形式）： \[S = (C_{in} \land \lnot A \land \lnot B) \lor (\lnot C_{in} \land \lnot A \land B) \lor (C_{in} \land A \land B) \lor (\lnot C_{in} \land A \land \lnot B)\] 但改用 XOR 就非常精簡： \[\boxed{S = A \oplus B \oplus C_{in}}\] 多輸入的 XOR 在奇數個輸入為 1 時輸出 1—— 正是「和位元」的行為（1 的個數為奇數時 \(S=1\)）。 棋盤式 K-map 正是 XOR 的signature：看到它就該想到 XOR。

全加器公式：Carry out

把 \(C_{out}\) 填入卡諾圖：

三個兩格的框（皆含右下角的 \(111\)）： \[C_{out} = (C_{in} \land B) \lor (A \land B) \lor (C_{in} \land A)\] 直覺讀法：「三個輸入中至少兩個為 1」（多數決函數）。 用分配律可改寫成： \[C_{out} \equiv (A \land B) \lor (C_{in} \land (A \lor B)) \equiv \boxed{(A \land B) \lor (C_{in} \land (A \oplus B))}\] 為什麼最後一步可以把 \(\lor\) 換成 \(\oplus\)？ 兩者只在 \(A = B = 1\) 時不同，而此時 \((A \land B) = 1\) 已讓整個式子為 1， 所以差異被吸收，結果不變。 工程上偏好 \(\oplus\) 版本：\(A \oplus B\) 這個訊號 在 Sum 電路（\(S = (A \oplus B) \oplus C_{in}\)）裡本來就有， 分支複用即可，省下一個閘。

用兩個半加器組全加器

• 半加器 1（左）：算 \(A \oplus B\) 與 \(A \land B\)；

• 半加器 2（中）：把 \(A \oplus B\) 與 \(C_{in}\) 相加， 得 \(S = A \oplus B \oplus C_{in}\) 與 \(C_{in} \land (A \oplus B)\)；

• OR 閘（右）：合併兩個進位， \(C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))\)—— 正是上一節的偏好公式！

漣波進位加法器（Ripple Carry Adder）

從加 2 個位元（\(A, B\)）進化到加 3 個位元（\(A, B, C_{in}\)）之後， 把全加器串接起來，就能加任意多位元的數：

二進位減法（Binary Subtraction）

減法就是加法

常用的帶號數表示法有三種： 符號-大小（sign-magnitude）、1 補數（1’s complement）、 2 補數（2’s complement）。前兩種各有缺陷，第三種是現代電腦的標準。

符號-大小（Sign-Magnitude）

值的表示方式與無號二進位相同，只是 MSB 改為代表正負號（0 正 1 負）：

4 位元可表示 \(+7\) 到 \(-7\)——只有 15 個數，但 4 位元明明有 \(2^4 = 16\) 種組合。 缺陷：0 有兩種表示： \[0000_2 = +0_{10} \qquad 1000_2 = -0_{10}\]

1 補數（1’s Complement）

負數定義為其正數版本的補數（complement）——把每個位元 \(0 \leftrightarrow 1\) 翻轉：

問題依舊：0 仍有兩種表示（\(0000\) 與 \(1111\)），沒有用滿整個範圍； 而且算術在 0 附近不一致——\(1111 + 1\) 會得到 \(0000\)（帶溢位）， 兩者在十進位裡都是 0，跨越 0 的加法需要額外修正。

2 補數（2’s Complement）

4 位元可表示 \(+7\) 到 \(-8\)：0 只有一種表示， 16 種組合全部用滿——比前兩種方案多出一個可表示的值。 正數的表示與無號二進位相同，但要注意至少補一個 0 當 MSB （否則 MSB 會被讀成負權重）。

減法電路

\[A - B \equiv A + (-B) \equiv A + (\text{NOT}(B) + 1)\]

要讓加法器架構支援減法，只需兩個小改動：

1. 用 NOT 閘把 \(B\) 的每個位元翻轉；

2. 漣波進位加法器第一個全加器的 \(C_{in}\) 本來閒置（原本接 0）—— 把它設成 1，正好完成「加 1」！

加減兩用器（adder-subtractor）： 只差一個「選擇要不要翻轉 \(B\) 並加 1」的機制。 標準做法（延伸補充）：加一條控制線 \(sub\)， 每個 \(B_i\) 先過一個 XOR 閘（另一輸入接 \(sub\)），\(sub\) 同時接到 \(C_{in}\)：

原理：\(B_i \oplus 0 = B_i\)（照常加法）、\(B_i \oplus 1 = \lnot B_i\)（翻轉）—— XOR 是「可控反相器」。\(sub = 0\) 時算 \(A + B\)； \(sub = 1\) 時算 \(A + \lnot B + 1 = A - B\)。一條線同時完成兩件事。

溢位（Overflow）

之前加法時我們把多出來的進位「先忽略」，現在它有了重要用途： 使用 2 補數加法時，溢位用來判斷「丟棄多餘位元後的結果是否正確」。

C 語言中的溢位

整數溢位是程式「莫名其妙不對」的常見原因：

int num = INT_MAX;
// prints the maximum value for an int (2147483647 for 32-bit int)
printf("%i\n", num);

num++;
// prints the value after overflow (-2147483648 for 32-bit int)
printf("%i\n", num);

\(2147483647 = 2^{31}-1\)（32 位元 int 的上限）加 1 後， 繞回到最小值 \(-2^{31} = -2147483648\)—— 正是「正 + 正 = 負」的溢位。兩點實務教訓：

• 寫程式時假設變數用最壞情況（最小）的記憶體大小儲存，比較安全；

• 同一段計算在 A 機器正常，搬到用更少記憶體存該型別的 B 機器上可能出錯。

定點數（Fixed-Point）

整數表示法無法表示非整數，會損失精度。 定點數（fixed-point）：與二進位相同， 但指定部分位元代表分數（仍是 2 的冪次，只是次方為負）：

小數點的位置由需求決定：範圍（range）——最大最小值， 與精度（precision）——值之間的增量。 上例（2 整數位 + 2 小數位）只能表示 \(0\) 到 \(3.75\)、增量 \(0.25\)。 若要負的分數，同樣可以讓 MSB 帶 2 補數的負權重。

浮點數（Floating-Point）

兩個關鍵設計：

• 偏移指數（biased exponent）：指數加上一個偏移量（bias）後儲存， 讓負指數也能存成正值（免去指數自己再帶一套符號系統）。 \(k\) 位元指數的 bias 為 \(2^{k-1}-1\)（3 位元 \(\Rightarrow\) bias \(= 3\)）。

• 正規化尾數（normalised mantissa）：把數字調整成 「小數點前恰有一個 1」（\(1.xxx_2 \times 2^E\)）—— 既然開頭必為 1，就不儲存這個隱含的前導 1，省一個位元的精度。

最常見的浮點精度由 IEEE 754 技術標準定義， 它同時規定了無限大（\(\infty\)）與 NaN（Not a Number）等特殊值的表示。

浮點誤差

浮點數的小數部分是負的 2 的冪次的選和 （\(2^{-1} = \tfrac12\)、\(2^{-2} = \tfrac14\)、\(2^{-3} = \tfrac18\)……）。 因此許多「看起來簡單」的分數無法精確表示、只能近似， 而某些「看起來複雜」的分數反而可以精確表示：

• \(0.1_{10}\)：二進位是無限循環的 \(0.000110011001100\ldots_2\)—— 任何有限位元的浮點格式都只能存近似值。 這正是著名的 0.1 + 0.2 != 0.3 問題的根源 （IEEE 754 雙精度下 \(0.1+0.2 = 0.30000000000000004\ldots\)）。

• \(0.375_{10} = 0.011_2 = 2^{-2} + 2^{-3}\)：有限、可精確表示 ✓。

算術邏輯單元（ALU）

什麼是 ALU？

兩個要點：

• 資料匯流排（data bus）：一次傳送多位元訊號的位元陣列 （圖中斜線記號表示多位元線）。

• 邏輯運算是逐位（bitwise）的： \(\text{out}_0 = x_0 \land y_0\)、\(\text{out}_1 = x_1 \land y_1\)……各位獨立； 算術運算則有進位在位元之間傳遞（第 2 章的漣波進位）。

控制位（Control Bits）

ALU 怎麼知道要算哪個函數？——用控制位（control bits，又稱 select bits）。 以本課程的 Hack ALU 為例，它用 6 個控制位，每個都是二選一：

處理順序是一條固定的管線（\(zx, nx\) 先於 \(zy, ny\) 並行，再 \(f\)、最後 \(no\)）：

多工器（Multiplexer）

控制位的「二選一」在硬體上如何實現？答案是多工器。

2 對 1 多工器只需 1 個選擇位： select \(= 0\) 輸出 input\(_0\)；select \(= 1\) 輸出 input\(_1\)。 布林式：\(\text{output} = (\lnot s \land i_0) \lor (s \land i_1)\)。 Hack ALU 的每個控制位背後就是一排（16 個位元同時切換的）2 對 1 MUX。

解多工器（Demultiplexer）

1 對 2 解多工器：select \(= 0\) 時輸入走 output\(_0\)、 select \(= 1\) 時走 output\(_1\)。 （MUX 是「多路進、選一路出」，DEMUX 是「一路進、選一路出去」—— 一對互為鏡像的流量指揮工具。）

Hack ALU

Hack ALU 的輸入輸出都是 16 位元資料匯流排上的 2 補數值。 把控制位設成下表的組合，就會計算出對應的函數 （這是精簡版；完整的 ALU 真值表還列出其他組合可得的更多函數）：

綜合練習題（附詳解）

練習 1：基底轉換

把 \(0b10110111\) 轉成十進位、十六進位與八進位。

練習 2：十進位轉二進位

把 \(77_{10}\) 轉成二進位（兩種方法各做一次），再寫出其十六進位。

練習 3：範圍計算

(a) 3 個位元組的無號整數能表示哪些值？ (b) 6 位元 2 補數的範圍？ (c) 為什麼 4 位元 2 補數能表示的值比符號-大小多一個？

練習 4：二進位加法與溢位

以 4 位元 2 補數計算下列各式，並判斷是否溢位： (a) \(0110 + 0111\)；(b) \(1100 + 1110\)；(c) \(0101 + 1011\)。

練習 5：2 補數轉換

(a) 求 \(-6\) 的 4 位元 2 補數。 (b) 求 \(-12\) 的 5 位元 2 補數。 (c) \(10110_2\)（5 位元 2 補數）是十進位多少？

練習 6：用加法器做減法

以 4 位元電路計算 \(6 - 2\)：寫出 \(A\)、\(\text{NOT}(B)\)、\(C_{in}\) 與逐位計算過程。

練習 7：全加器公式

只用真值表驗證 \(C_{out} = (A \land B) \lor (C_{in} \land (A \oplus B))\) 與 K-map 求出的 \((C_{in} \land B) \lor (A \land B) \lor (C_{in} \land A)\) 等價。

練習 8：定點數

用「2 整數位 + 2 小數位」的定點格式： (a) 表示 \(2.5\)；(b) \(1.3\) 能精確表示嗎？最接近的值是？ (c) 這個格式的範圍與精度各是多少？

練習 9：浮點數編碼

用第 3 章的 S(1)–E(3)–M(4) 格式（bias \(= 3\)）： (a) 編碼 \(5.5\)；(b) 解碼 \(1\,011\,1000\)。

練習 10：MUX 與 DEMUX

(a) 8 對 1 多工器需要幾個選擇位？ (b) 寫出 2 對 1 MUX 的布林式並化成最少的閘。 (c) 用 MUX 的觀點解釋 Hack ALU 的 \(f\) 控制位。

練習 11：Hack ALU 控制位推導

不查表，推導出讓 Hack ALU 輸出下列函數的控制位： (a) 常數 \(0\)；(b) \(\lnot x\)；(c) \(y - x\)。

練習 12：溢位觀念題

一個程式在 64 位元機器上把兩個大整數相加結果正確， 搬到 32 位元機器卻輸出負數。解釋原因，並提出兩種對策。

附錄：速查表

2 的冪次表

各表示法對照（4 位元）

加法器公式速查

名詞中英對照

參考資料

• Kira Clements, COMSM1302 Week 2 lecture slides（2.1–2.4），University of Bristol.

• Nisan & Schocken, The Elements of Computing Systems（nand2tetris）， Ch. 2 Boolean Arithmetic（Hack ALU 完整規格與 HDL 實作）.

• IEEE 754 技術標準；Wikipedia：Single-precision floating-point format.

• Exploring Binary，Why 0.1 Does Not Exist in Floating-Point.

• Wikipedia：Adder (electronics)、Carry-lookahead adder、 Two’s complement.