# 2026q1 Homework2 (stdc)
contributed by<[winterchen](https://github.com/kstoko02)>

{%hackmd NrmQUGbRQWemgwPfhzXj6g %}
> 課程助教註記: 4 月 14 日

## 細讀〈[你所不知道的 C 語言：數值系統篇](https://hackmd.io/@sysprog/c-numerics)〉
* 教材以 `0.1 + 0.2 ≠ 0.3` 作為引言，說明電腦的數值表示問題，援引 IEEE 754 規格和你在電腦上的實驗，充分回答以下:
- [x] 為何十進位的 `0.1` 無法在二進位浮點數中精確表示？用 Graphviz 或類似的向量繪圖表示法，清晰展現數值表示的過程和限制

電腦使用 IEEE 754 的二進位浮點數來表示實數，但像 0.1 這種十進位小數在二進位中會變成無限循環小數，因此無法被精確儲存，只能經過截斷並搭配四捨五入後，存成一個最接近的近似值。

此流程表示將十進位數轉為可能無限長的二進位後，因精度限制先截斷，再依規則四捨五入成最接近的可表示浮點數。

    graph TD
    A["十進位數 (例如 0.1)"] --> B[轉換為二進位]
    B --> C[得到無限循環小數]
    C --> D[依 IEEE 754 精度限制截斷]
    D --> E{被截掉的部分 >= 1/2 ULP?}
    E -- 是 --> F["進位(Round Up)"]
    E -- 否 --> G["不進位(Truncate)"]
    F --> H[儲存為最接近值]
    G --> H
    H --> I[最終浮點數表示]

- [x] IEEE-754 單精度或雙精度為例，說明 sign, exponent, mantissa 在表示 `0.1` 時會發生什麼情況。

IEEE 754 浮點數：
$$
\text{value} = (-1)^s \times 1.f \times 2^e
$$

將 0.1 正規化 :
$$
0.000110011...=1.100110011...×2^{−4}
$$

單精度(bias = 127) :
| 欄位 | bits | 值 | 說明 |
| -------- | ---- | ----------------------- | ------------------------ |
| sign | 1 | 0 | 正數 |
| exponent | 8 | 01111011 | = 123（bias 127 → 實際為 -4） |
| mantissa | 23 | 10011001100110011001101 | 來自 0.1 的無限循環截斷 |

- [ ] 文中指出浮點數加法不具有結合律，從 Linux 核心的原始程式碼 (事實上使用定點數，但具備浮點數運算的特性) git log 找出對應的浮點數運算考量並充分討論

* 針對 balanced ternary 和 radix economy
- [x] 電腦科學家 Donald E. Knuth 在《The Art of Computer Programming》第 2 卷說 "Perhaps the prettiest number system of all is the balanced ternary notation"，其背景考量是什麼？Knuth 是否有對應的著作進一步探討？

《The Art of Computer Programming》 中提到：
>Perhaps the prettiest number system of all is the balanced ternary notation,which consists of radix-3 representation using −1, 0, and +1 as “trits” (ternary digits) instead of 0, 1, and 2.

一般的三進位使用 $0$，$1$，$2$ 作為數字，而平衡三進位則是以 $0$ 為中心，使用 $-1$，$0$，$1$ 作為基本單位（通常記作 $\bar{1}, 0, 1$ 或 $-, 0, +$）。

舉例：
將十進位的 $14$ 轉為[平衡三進位](https://zh.wikipedia.org/zh-tw/%E5%B9%B3%E8%A1%A1%E4%B8%89%E9%80%B2%E4%BD%8D)：
1. 先將十進位轉換為「普通的三進位」，$14_{10} = 1 \times 9 + 1 \times 3 + 2 \times 1 = \mathbf{112_3}$
2. 加上一個由無限個（或足夠多個）1 組成的數字，$112_3 + 1111_3 = \mathbf{2000_3}$
3. 將結果的「每一個位數」減 1，$2000_3$ 的每一個數字都減 1（$2 \rightarrow 1$，$0 \rightarrow \bar{1}$），
得到結果：$\mathbf{1\bar{1}\bar{1}\bar{1}}$，在平衡三進位中等於 $(1 \times 27) + (-1 \times 9) + (-1 \times 3) + (-1 \times 1) = 27 - 13 = \mathbf{14}$

>The balanced ternary number system has many pleasant properties:
a) The negative of a number is obtained by interchanging 1 and 1.
b) The sign of a number is given by its most significant nonzero trit, and in general we can compare any two numbers by reading them from left to right and using lexicographic order, as in the decimal system.
c) The operation of rounding to the nearest integer is identical to truncation; in other words, we simply delete everything to the right of the radix point.

上述為原文書中提到使用平衡三進位的特性：
a) 假設要算 $-14$，只要把 $14$ 的 $1\bar{1}\bar{1}\bar{1}$ 反轉成 $\bar{1}111$ 即可。硬體設計師不需要設計複雜的二補數電路。
b) 在二進位中，比大小有時需要考慮符號位元，如果是浮點數就更複雜，但在平衡三進位中，最左邊的第一個非零數字就決定了這個數字是正還是負。
c) 在平衡三進位中，小數點後面的最大極限值是 $0.1111..._3$，這在數學上剛好等於十進位的 $+0.5$；最小極限值 $0.\bar{1}\bar{1}\bar{1}..._3$ 剛好等於 $-0.5$。這說明平衡三進位的小數部分永遠被限制在 $[-0.5, 0.5]$ 之間，所以當四捨五入成整數時，不需要寫判斷式去檢查小數點後大於還是小於 5，直接把小數點後面的值砍掉，留下來的整數必定會是最接近的整數。
- [x] 為何 balanced ternary 中求負數只需「符號反轉」？與二補數 (two's complement) 表示法相比，分析計算成本、硬體實作，和數值對稱性。建立數學模型並討論

**平衡三進位的模型**：
在一個 $n$ 位的平衡三進位系統中，任何整數 $V$ 可以表示為底數 $3$ 的多項式：
$$
V = \sum_{i=0}^{n-1} d_i \cdot 3^i
$$
其中，每一個位元的係數 $d_i \in \{-1, 0, 1\}$。
當我們要求這個數字的負數 $-V$ 時，根據代數分配律，我們只需將負號分配到每一個項式中：
$$
-V = -\left( \sum_{i=0}^{n-1} d_i \cdot 3^i \right)
= \sum_{i=0}^{n-1} (-d_i) \cdot 3^i
$$
因為 $d_i$ 只有 $-1, 0, 1$ 三種狀態，所以 $-d_i$ 就是直接將 $1$ 變成 $-1$，$-1$ 變成 $1$，$0$ 保持不變。

**二補數的模型**：
在一個 $n$ 位的[二補數](https://zh.wikipedia.org/zh-tw/%E4%BA%8C%E8%A3%9C%E6%95%B8)二進位系統中，最高位（$b_{n-1}$）是符號位，帶有負權重。數值 $V$ 表示為：
$$
V = -b_{n-1} \cdot 2^{n-1} + \sum_{i=0}^{n-2} b_i \cdot 2^i
$$
其中 $b_i \in \{0, 1\}$。
在二進位中，因為沒有 $-1$ 這個符號無法直接對位元加上負號。為了解決這個問題，數學上利用了位元反轉的特性，$x + \sim x = -1$ 推導出求負數的公式：
$$
-V = \text{NOT}(V) + 1
$$
因此二補數求負數必須分為兩步：先對所有位元進行布林反轉（0 變 1，1 變 0），然後加上 1。

**數值對稱性**：
*平衡三進位*： 一個 $n$ 位的系統，其表示範圍是 $[-\frac{3^n - 1}{2}, \frac{3^n - 1}{2}]$。正數和負數的數量完全一樣多（中間夾著一個 0），最大的正數取負號，剛好等於最大的負數。
*二補數*： 一個 $n$ 位的系統，其表示範圍是 $[-2^{n-1}, 2^{n-1} - 1]$，負數永遠比正數多一個。例如 8-bit 的範圍是 $[-128, 127]$，如果對 $-128$ 取負數，系統會發生溢位變回 $-128$。

**計算成本**:
*平衡三進位*： 因為求負數只需「符號反轉」，無論數字有 8 位還是 64 位，所有的位元反轉可以在同一個時鐘週期內完成，時間複雜度為 $\mathcal{O}(1)$。
*二補數*： 致命傷在於「$+1$」。加法從最低有效位開始，若產生進位，進位可能一路傳遞到最高位，其延遲時間在理想情況下為 $\mathcal{O}(n)$，即便採用[超前進位加法器](https://zh.wikipedia.org/zh-tw/%E5%8A%A0%E6%B3%95%E5%99%A8)將最壞情況延遲優化至 $\mathcal{O}(\log n)$ 在計算成本和電路延遲上，依然遠大於平衡三進位的 $\mathcal{O}(1)$。

**硬體實作**：
*平衡三進位*：實作三進位需要在電路中區分三種狀態（例如正電壓、零電壓、負電壓），在奈米級距的晶片中穩定控制三種電壓，並且保證不會因為溫度或電磁干擾而互相誤判，製程難度與成本高得驚人。蘇聯雖然曾在 1950 年代造出 [Setun](https://en.wikipedia.org/wiki/Setun) 三進位電腦，但最終仍因硬體可靠度與生產成本無法與二進位體系競爭而遭到淘汰。
*二補數*：二進位依賴電晶體的「開（高電位）」與「關（低電位）」，形成清晰的兩態邏輯（0/1），此狀態非常穩定，抗雜訊能力極強。雖然在演算法上需要一個加法器來處理「$+ 1$」，但 CPU 本來就需要加法器來算加減法，所以直接共用同一個 ALU 即可，硬體成本極低。

- [ ] 說明為什麼低位元量化 (例如 ternary / 1-bit LLM) 在 AI 硬體中具有潛在優勢。參照提及的論文，描述其關鍵考量 $\to$ 歡迎協作 [BitMamba.c](https://github.com/jserv/bitmamba.c)

* 算術運算可完全以數位邏輯實作，分析 $x + y = (x \oplus y) + ((x \& y) << 1)$ 並回答：
- [x] 參閱數位邏輯教科書 (善用圖書館資源)，在硬體加法器中 `x ^ y` 和 `x & y` 各代表什麼訊號？並摘錄書中對應的描述，探討其應用場景

參閱《Digital Design》 by M.Morris Mano，在4-3 ADDERS 章節中對半加法器的描述：
> A combinational circuit that performs the addition of two bits is called a half-adder.
> The input variables designate the augend and addend bits; the output variables produce the sum and carry. It is necessary to specify two out- put variables because the result may consist of two binary digits. We arbitrarily assign symbols x and y to the two inputs and S (for sum) and C (for carry) to the outputs.
> The carry output is 0 unless both inputs are 1. The S output represents the least significant bit of the sum.
The simplified Boolean functions for the two outputs can be obtained directly from the truth table. The simplified sum of products expressions are
S = x'y + xy'
C = xy

`x ^ y`：代表「不帶進位的和」， 當 $x$ 和 $y$ 的位元不同時的結果是 1，相同時的結果是 0
`x & y`：代表「進位訊號」，只有當 $x$ 和 $y$ 都是 1 的時候，才需要向左邊進位 1

對全加法器的描述：
>A full-adder can be implemented with two half-adders and one OR gate, as shown in Fig. 4-5.

一個全加法器可以由兩個半加法器及一個 OR 邏輯閘組成，進而可串成漣波進位加法器或超前進位加法器。

- [x] 為何 `(x+y)/2` 可能造成 overflow？又為何 $(x \& y) + ((x \oplus y) >> 1)$ 可避免 overflow

在 C 語言中，暫存器和變數的位元寬度是有限的，假設使用 8-bit 的無號整數，最大能表示的數值為 255。
令 $x = 200$, $y = 100$，預期的平均數應為 $\frac{300}{2} = 150$。
但當執行 `x + y` 時，$200 + 100 = 300$ 超出了 8-bit 的極限 (255)。硬體會發生溢位，將超出 8-bit 的部分截斷，實際儲存的結果變成 $300 \pmod{256} = 44$。
接著執行除以 2：$\frac{44}{2} = 22$，這導致程式邏輯錯誤。

從 $x + y = (x \oplus y) + ((x \& y) << 1)$ 公式推導：
$$
x + y = 2 \times (x \mathrel{\&} y) + (x \oplus y)
$$
移項得到
$$
\frac{x + y}{2} = (x \mathrel{\&} y) + \frac{x \oplus y}{2} = (x \& y) + ((x \oplus y) >> 1)
$$
在位元運算中，除以 2 就等同於向右平移一位（>> 1）。
因 `x & y` 的結果絕對小於等於 $\min(x, y)$ 且 `(x ^ y) >> 1` 的結果絕對嚴格小於 $\max(x, y)$，兩者相加的結果，上述已證明剛好等於平均值，且在運算的任何一個步驟，數值都不會超越原本的 $x$ 或 $y$，因此絕對不會溢位。

- [ ] 在 Linux 核心中，為何這類 bit-level reasoning 對於效能與正確性非常重要？在 git log 找出對應的改進和修正

* `x & (x - 1)` 可用來檢測什麼數值性質？給出數學推導，說明為何此技巧成立。Linux 核心中有哪些場景會利用 power-of-two (2 的冪，[不是「冪次」](https://hackmd.io/@sysprog/it-vocabulary)) 性質？為何 power-of-two 對於系統效能特別重要？
* `((X) - 0x01010101) & ~(X) & 0x80808080` 技巧可用於 `strlen()` 的實作，回答：
* 該巨集偵測的是什麼資料？為何該運算可一次檢測 4 個位元組？為何這比逐 byte 檢查更有效率？
* 在 Linux 核心原始程式碼中找出類似 word-at-a-time 手法的案例，並充分進行效能分析
* 教材提及若干真實案例，以 Boeing 787 的[軟體缺失案例](https://hackmd.io/@sysprog/software-failure)來說，為何 32 位元計數器在約 248 天會 overflow？參照 FAA (Federal Aviation Administration ) 和相關官方事故分析報告進行探討
* 在 Linux 核心的 git log 找出類似的 integer overflow 案例並探討
* 在 C 語言規格書列舉相關整數範圍的規範和實作考量

## 參考資料
* [[1] Setun](https://en.wikipedia.org/wiki/Setun)