CS:APP 第 2 章重點提示和練習

資料整理: jserv

千萬不要小看數值系統，史上不少知名 軟體缺失案例 就因為開發者未能充分掌握相關議題，而釀成莫大的傷害與損失。

數值系統

• 導讀

• video: 10 進位、16 進位，和 60 進位從何而來？
• video: 老鼠和毒藥問題怎麼解？二進位和易經八卦有啥關係？
  • 萊布尼茲並非首位使用二進位系統表示數字的人，但他是第一個看出二進位優勢，並有系統地建構二進位算術的人。1679 年 3 月，他撰寫了〈關於二進位制〉(On the Binary Progression) 的手稿，詳述如何透過不斷除以 2，將十進位的數字轉換為二進位數字。每步的餘數，0 或 1，便組成最終的二進位數字。他也詳細描述二進位的加減乘除法則。
  • 萊布尼茲深知，二進位運算的規則雖然簡單，但隨著數字變大，計算的耗時往往超過十進位制。然而，對於機械計算來說，這種限制並非問題。事實上，早在巴黎時期，他便曾改良巴斯卡 (Blaise Pascal) 發明的加法器，製作出能進行二位數乘除運算的木製計算機。這台原型機使用齒輪進行十進位計算，而如果要讓機械進行二進位運算，則需要全新的設計。
  • 在同一篇手稿中，萊布尼茲設想一種特殊的木盒裝置，其中包含許多格子，代表二進位的各個位數。格子裡若放有圓球，則表示 1，否則為 0。每個格子的底板可活動，當打開時，圓球會掉落下去。透過這種裝置，他構想出進行二進位數值運算的機械計算機。然而，僅停留在概念階段，萊布尼茲並未繪製實際的設計圖。
  • 1701 年，萊布尼茲完成二進位算術的論文，提交給巴黎皇家科學院 (即法國科學院)，卻被秘書長以「無法看出二進位有何用途」為由拒絕。起初，萊布尼茲打算就此放棄，不過二年後，來自中國的信改變一切。1697 年起，法國傳教士白晉 (Joachim Bouvet) 與萊布尼茲保持通信。在 1701 年的信中，白晉提及《易經》中卦象是由陰陽兩爻組成，並附上六十四卦的版畫。萊布尼茲在 1703 年初收到這封信後，大受啟發，決定利用中國的易經卦象，來宣揚二進位。他重新撰寫論文，引用伏羲八卦圖作為例證，以增加說服力。終於，二進位算術得以重見天日。
  • 一百多年後，英國數學家布爾 (George Boole) 基於這一概念，於 1847 年提出布林代數 (Boolean Algebra)，這成為了現代數位計算機的運算基礎。
• video: 小精靈遊戲中的幽靈是怎麼追蹤人的? 鮮為人知的 bug
  • 經典電玩遊戲小精靈 (Pac-Man) 的實作也有 integer overflow，致使畫面顯示錯亂 (但仍可繼續玩)
• 解讀計算機編碼
• Binary and Number Representation 記得要按右下方的 Next
• C 語言: 未定義行為
• 基於 C 語言標準研究與系統程式安全議題
• 重新理解數值 之後你可以做什麼？思考更直接的手法去操作每個位元
  • Better Alternative to Integer Modulo
• 熟悉浮點數每個位元的表示有何好處？更大的最佳化空間
  • Faster arithmetic by flipping signs
  • Faster floating point arithmetic with Exclusive OR

• 圖解
  

出處

• Bits, Bytes & Integers

第一部分錄影 / slides

• 無號整數表示法少了正負號位元，而有號整數表示法中的位元分以下 3 種：
  1. 正負號
  2. 值
  3. 填充
• 正負號和值的格式可以是以下 3 類之一:
  • 二補數 (two's complement; 中國翻譯為「補碼」)
  • 一補數 (ones' complement; 中國翻譯為「反碼」，注意 "s" 字母的位置)
  • 正負號加上大小 (原碼)
• 無號整數表示法則少了正負號位元

• 重新思考負數的定義 (採用二補數的考量)

以二進位來表示數字，以三碼為例，則有 0~7 共 8 個數字可定義。但若要定義負數，則取首碼來表示正負（0 為正、1 為負），後兩碼對應數字，共可定義 -4 ~ +3 同樣共 8 個數字；然而其中負數最大的是 -1，故以 １１１ 訂之，負數中最小的是 -4，以 １００ 訂之，其餘依大小類推，確保二進位與十進位的大小加減方向相同。而非直接以後兩碼的二進位數字表示。

由上方對稱性可知，例如將 3 的二進位表示 ０１１ 完全翻轉成 １００ 之後，對應的是 -4（而非 -3！這是由於為了把 0 定義進來，導致正負數範圍不對稱），因此只要再加 １ 上去，就會變成 -3 的二進位表示 １０１ 了！即：

０１１(+3₁₀) ──翻轉─→ １００ (-4₁₀) ──再加１─→ １０１(-3₁₀)

這就是從 +3 取其二補數得到 -3 的過程。

這定義也使得負數自動符合減法運算：只要再加上一個條件「溢位就忽略掉」。運算結果就只會在 -4 ~ +3 之間循環。

例如運算 2 + (-3)，在二進位的運算即對應 ０１０ + １０１，這其實在原本二進位的無號數定義中是 2 + 5 的意義。但因溢位就忽略掉造成的循環，我們發現 +5 的運算和 -3 兩者在運算上等價，也就是說，在這些運算之中：

• +4 與 -4 效果相同
• +5 與 -3 效果相同
• +6 與 -2 效果相同
• +7 與 -1 效果相同

因此原本二進位無號數下半部的加法操作，可以直接照搬過來視為二進位有號數的減法操作。

補充資訊: Bit-Level Representation of Two’s Complement Negation

• 延伸閱讀
  • N1256 6.2.6.2 p1~p2
  • C Defect Report #069

不是所有的位元組合都能表示合理的數字，存取某些位元組合在特定機器上可能會造成嚴重錯誤，此種組合稱作陷阱表示法 (trap representation)。除非使用位元運算或是違反標準其他規定 (如溢位)，一般的運算不可能產生陷阱表示法。

C 語言標準明確允許實作自行決定在以下兩種狀況下是否是陷阱表示法：

• 型態為有號整數且正負號及值位元為特定組合時 (三種格式各有一特殊組合)
• 填充位元為某些組合時 $\to$ N1256 註腳# 44, 45

位元運算會忽略填充位元，因此（等級不低於 unsigned int 的）無號整數可安心使用。為求最大可攜性，位元運算不應該用在有號整數上。

在 C11 規格 6.2.6.2 Integer types 指出

For unsigned integer types other than unsigned char, the bits of the object representation shall be divided into two groups: value bits and padding bits (there need not be any of the latter). If there are N value bits, each bit shall represent a different power of 2 between 1 and 2^N−1, so that objects of that type shall be capable of representing values from 0 to 2^N−1 using a pure binary representation; this shall be known as the value representation. The values of any padding bits are unspecified.

uintN_t 和 intN_t 保證沒有填充位元，intN_t 一定是二補數，而且 intN_t 不可能有陷阱表示法，堪稱是最安全的整數型態。實作可能不提供這些型態，不過一旦提供，即保證符合性質。 $\to$ N1256 7.18.1.1 p1~p3

注意：直到 C23 標準，C 語言才全面採納二補數系統，之前顧及相容性議題，允許一補數的存在。

位移運算子(Shift operator):

• 左移: x << y : x 左移 y 位元，左移出的位元會被丟棄，右側會補上 0
• 右移: x >> y : x 右移 y 位元，右移出的位元會被丟棄。

兩種位移:

• 邏輯位移 (Logical shift) : 左側會補上 0
• 算術位移 (Arithmetic shift) : 補上號數 (sign bit) 也就是最高有效位元的值在左側

例:
X = 10100010;
Logical shift: x >> 2 = 00101000
Arithmetic shift: x >> 2 = 11101000

注意位移運算的兩種未定義狀況

• 左移超過變數長度，其結果未定義;
  ​​​​int i=0xFFFFFFFF;
  ​​​​i = i << 32; // 此結果未定義
  

• 右移一個負數時，可能是邏輯位移或是算術位移，C 語言標準未定義;

算術位移的應用，若要判斷一個 int 型態的變數 n 是否為正數，可用 n >> 31 其等價於 n >=0 ? 0: -1.

• 右移如果是一個負數時，會變成正或著是負值，要注意編譯器如何實作。編譯器甚至可以有編譯選項可改變此語意，gcc 的實作上是使用 arithmetic shift。

有號數 x 到無號數 (U 結尾) 映射機制：非負數不變為 x，負數轉換為大的正數 (x + 2^w，最靠近 0 的負數映射最大，最小的負數被映射為剛好在二補數表達之外的無符號數)。

• 例如 w = 4，二補數能表示的有號數範圍是 -8 [1000] ～ 7 [0111]

當無號數與有號數在 C 語言混合在單一表示式時，有號數會被轉換為無號數。在運算子操作時會有些意外的結果。有號數負值會因為轉換成 2 補數後，反而負值會大於正值。因此要注意混用時的運算狀況。
案例:

變數 1	變數 2	比較結果	轉換後
0	0U	==	unsigned
-1	0	<	signed
-1	0U	>	unsigned
2147483647	-2147483647-1	>	signed
2147483647U	-2147483647-1	<	unsigned
-1	-2	>	signed
(unsigned)-1	-2	>	unsigned
2147483647	2147483648U	<	unsigned
2147483647	(int) 2147483648U	>	signed

一個有號數意外結果的例子。

int n = 10; 
for (int i = n - 1 ; i - sizeof(char) >= 0; i--)
    printf("i: 0x%x\n",i);

這個例子會造成無窮迴圈，因為 sizeof 會回傳值是 unsigned int 型態，i 變數也會被轉換為 unsigned 的形式，無號數 0 再減 1 就會變為 0xFFFFFFFF 而產生無窮迴圈。

在有號整數上都可能產生陷阱表示法
補充資訊: Writing TMin in C

• Figure 1 列出 ISO C90 和 ISO C99 對於資料型態定義的落差
• 注意 Implications

延伸閱讀: Signed and Unsigned Numbers

在 Whirlwind Tour of ARM Assembly 指出，若 n 是有號 32-bit 整數，那麼 n >> 31 相當於 n >= 0 ? 0 : -1

bitwise left shift operation invokes Undefined Behaviour when the left side operand has negative value
Weird behavior of right shift operator (1 >> 32)

若 n 是 32-bit 整數，那麼 abs(n) 等同於 ((n >> 31) ^ n) - (n >> 31)

• 當 n 是正數時:
  • n >> 31 是 0;
  • n ^ 0 是 $n$;
  • n - 0 仍是 $n$
• 當 n 是負數時:
  • n >> 31 是 -1;
  • -1 以 2 補數表示為 0xFFFFFFFF;
  • n ^ (-1) 等同於 1 補數運算;
  • 最後再減 -1，得到 2 補數運算的值

例如: unsigned int to unsigned short

第二部分錄影 / slides
對應 CS:APP3e 的第 2 章: 2.3 整數運算 (Page 60)

補充資訊: More on Boolean Algebra and Boolean Rings

• Properties of Boolean Algebras and Rings
• Representing and Manipulating Sets

用 XOR 檢查加法後是否有溢位

long a, b, x;
x = a + b;
if ((x ^ a) >= 0 || (x ^ b) >= 0)
    ...

檢查是否有加法導致的溢位：

1. 兩個正數相加變成負數表示溢位
2. 兩個負數相加變成正數也表示溢位

除了這兩者外沒有其它情況。綜合上述的條件，可簡化成：兩數相加後的正負號和原本兩者都不同 $\to$ 溢位
採用二補數系統，最高 bit 作為是 sign bit，XOR 剛好可滿足簡化的條件，其它 bit 無關緊要，運算完看 sign bit 即可。

一補數具有兩個 0 (即 +0 和 -0)，加法器進行減法時，往往需要一個額外的步驟，調整為單一表示法。二補數即可避免這問題，因此現代資訊系統無論是程式語言的整數表示或加法器的實作，幾乎皆採用二補數表示法。

在運算表達中，倘若其中一個為有號型態 (signed)，編譯器會 implicitly 將有號轉為無號運算。

• -1 < 0U 為 False
• -2147483647 - 1 (轉換為無號數相當於 2³²）== 2147483648U 為 True

這種轉換帶來的錯誤有時很難發現，避免的方法是，不該濫用無號數。

Don't use unsigned without understanding implications

• Easy to make mistakes

for (unsigned i= cnt - 2; i >= 0; i--)
    a[i] += a[i+1];

• Can be very subtle

#define DELTA sizeof(int)
for (int i= CNT; i - DELTA >= 0; i-= DELTA)

Counting Down with Unsigned

• Proper way to use unsigned as loop index

for (unsigned i = cnt - 2; i < cnt; i--)
    a[i] += a[i + 1];

• C Standard guarantees that unsigned addition will behave like modular arithmetic

  0 –1

  UMax

• 最好改為:

  ​​​​for (size_t i = cnt - 2; i < cnt; i--)
  ​​​​    a[i] += a[i + 1];
  

  • size_t 定義為 unsigned 並與 word size 等寬
  • 即便 cnt = UMax 時也能運作
  • 倘若 cnt 有號且 < 0 呢？

• int 只保證能存下 -2¹⁵ + 1 (-32767) 到 2¹⁵ - 1 (32767) 之間的整數，16 位元已足夠

  • 這也是為何 int 不一定是 32 位元

• int_least32_t 和 int_fast32_t (C99 開始引入的 fixed width integer types) 可保證存下至少 -2³¹ + 1 到 2³¹ - 1 之間的整數

  • 由於不一定是沒有陷阱表示法的二補數，所以保證範圍的下限不是 -2³¹，而是 -2³¹ + 1

bi-endianness (沒打錯，是 bi，而非 "big")

• 為了提高應用場域的效能和相容性，許多硬體架構如 Power, MIPS, ARM, 可透過特定的切換，支援 big, little 這兩種 byte-order

宋代學者趙與時在《賓退錄》說：「讀諸葛孔明《出師表》而不墮淚者，其人必不忠」，台灣人宅色夫在「Linux 核心設計」說：「讀 CS:APP 而不墮淚者，其人必不智」

終於知道為何我們研究生追求達到 CMU 大學部二年級程度是多麽偉大的目標吧？

• 練習題 2.30: tadd_ok (Page 65)

#include <stdbool.h>
bool tadd_ok(int x, int y) {
    int sum = x + y;
    bool over_neg = (x < 0) && (y < 0) && (sum >= 0);
    bool over_pos = (x >= 0) && (y >= 0) && (sum < 0);
    return (!over_neg) && (!over_pos);
}

浮點數

• 導讀

  • 從根號 2 的運算談浮點數
  • 對應 CS:APP 3/e 的 2.3.6 (Page 70-74), 2.4.5 (Page 85-87)
  • 使用浮點數最最基本的觀念

  「有理數」詞源

  有理數一詞源於《幾何原本》，在希臘文中稱為 λόγος (lógos)，原意指「成比例的數」。英文取其意，以 ratio 為字根，在字尾加上 -nal 構成形容詞，全名為 rational number，直譯成漢語即是「可比數」。對應地，無理數則為「不可比數」。明末數學家徐光啟和學者利瑪竇翻譯《幾何原本》前 6 卷時的底本是拉丁文。他們將 λόγος 對應的拉丁文 ratiō 譯為「理」，這個「理」指的是「比值」，但文言文中「理」字卻沒有比值的意思，於是這項翻譯缺失就承襲至今。

• Floating Point

錄影 / slides
對應 CS:APP3e 的第 2 章: 2.4.2 IEEE 浮點數表示 (Page 78), 2.4.5 浮點運算 (Page 85)

rounding error

• 電腦科學家制定如IEEE754之計算機標準，來表示實數家族中的小數，因為小數的數量是不可數無限的，而電腦中浮點數的數量是有限的，浮點數儲存的是個近似值，使用上會產生誤差。

3 種浮點型態

• denormalized
• normalized
• special

"Normalized" Values
When: exp≠ 000…0 and exp≠ 111…1

Denormalized Values
Condition: exp = 000…0
Exponent value: E= 1 –Bias (instead of exp–Bias)

Special Values
Condition: exp= 111…1

• 阿貝爾群也稱為可交換群 (commutative group)

IEEE 754 浮點數值的比較，需要考慮到 sign + magnitude，實際操作類似以下:

#define FasI(f)  (*((int *) &(f)))
#define FasUI(f) (*((unsigned int *) &(f)))

#define	lt0(f)	(FasUI(f) > 0x80000000U)
#define	le0(f)	(FasI(f) <= 0)
#define	gt0(f)	(FasI(f) > 0)
#define	ge0(f)	(FasUI(f) <= 0x80000000U)

• 練習題 2.58: 撰寫函式 is_little_endian，在 Little endian 機器上返回 1，反之返回 0，應能在任意機器、無論幾位元的架構都適用 (Page 88)
• 練習題 2.66: 撰寫函式 leftmost_one，產生得以找出數值 x 最高位 1 的位元遮罩 (Page 90)

  參考解

• 2018q1 第 2 週測驗題

  參考解

• 2018q1 第 3 週測驗題

  參考解