# [CS:APP](https://hackmd.io/c/S1vGugaDQ/) 第 2 章重點提示和練習 :::success 資料整理: [jserv](http://wiki.csie.ncku.edu.tw/User/jserv) :warning: 千萬不要小看數值系統,史上不少知名 [軟體缺失案例](https://hackmd.io/s/B1eo44C1-) 就因為開發者未能充分掌握相關議題,而釀成莫大的傷害與損失。 ::: ## 數值系統 * 導讀 * video: [10 進位、16 進位,和 60 進位從何而來?](https://www.youtube.com/watch?v=8J7sAYoG50A) * video: [老鼠和毒藥問題怎麼解?二進位和易經八卦有啥關係?](https://www.youtube.com/watch?v=jYQEkkwUBxQ) * video: [小精靈遊戲中的幽靈是怎麼追蹤人的? 鮮為人知的 bug](https://www.youtube.com/watch?v=CjXsHl88iI4) * 經典電玩遊戲小精靈 (Pac-Man) 的實作也有 integer overflow,致使畫面顯示錯亂 (但仍可繼續玩) * [解讀計算機編碼](https://hackmd.io/s/rylUqXLsm) * [Binary and Number Representation](https://www.bottomupcs.com/chapter01.xhtml) :notes: 記得要按右下方的 Next * [重新理解數值](https://hackmd.io/s/BkRKhQGae) * [C 語言: 未定義行為](https://hackmd.io/s/Skr9vGiQm) * [基於 C 語言標準研究與系統程式==安全議題==](https://hackmd.io/s/S15o_K3cQ) - [ ] Bits, Bytes & Integers :::info [第一部分錄影](https://youtu.be/wb2u59QF2iY) / [slides](https://www.cs.cmu.edu/~213/lectures/02-bits-ints-part1.pdf) ::: * 無號整數表示法少了正負號位元,而有號整數表示法中的位元分以下 3 種: 1. 正負號 2. 值 3. 填充 * 正負號和值的格式可以是以下 3 類之一: * 二補數 (two's complement; 中國翻譯為「補碼」) * 一補數 (ones' complement; 中國翻譯為「反碼」,注意 "s" 字母的位置) * 正負號加上大小 (原碼) * 無號整數表示法則少了正負號位元 - [ ] 重新思考負數的定義 (採用二補數的考量) 以二進位來表示數字,以三碼為例,則有 0~7 共 8 個數字可定義。但若要定義負數,則取首碼來表示正負(0 為正、1 為負),後兩碼對應數字,共可定義 `-4` ~ `+3` 同樣共 8 個數字;然而其中負數最大的是 `-1`,故以 `111` 訂之,負數中最小的是 -4,以 `100` 訂之,其餘依大小類推,確保二進位與十進位的大小加減方向相同。而非直接以後兩碼的二進位數字表示。 ```graphviz digraph structs { labelloc="t"; label="無號數 / 有號數\n加減法原理"; graph [nodesep="0.5", pencolor=transparent]; node [shape=record]; edge [ arrowhead="none"]; struct1 [label="{<c0>000|<c1>001|<c2>010|<c3>011|<c4>100|<c5>101|<c6>110|<c7>111}|{0|1|2|3|4|5|6|7}"]; arrow [shape=rarrow, style=filled, label=""]; struct2 [label="{<f0> +0|<f1>+1|<f2>+2|<f3>+3|<f4>-4|<f5>-3|<f6>-2|<f7>-1}"]; struct1:c0 ->struct1:c7; struct1:c1 -> struct1:c6; struct1:c2 -> struct1:c5; struct1:c3 -> struct1:c4; } ``` 由上方對稱性可知,例如將 3 的二進位表示 `011` 完全翻轉成 `100` 之後,對應的是 `-4`(而非 `-3`!這是由於為了把 0 定義進來,導致正負數範圍不對稱),因此只要再加 1 上去,就會變成 `-3` 的二進位表示 `101` 了!即: 011(==+3~10~==) ──翻轉─→ 100 (-4~10~) ──再加1─→ 101(==-3~10~==) 這就是從 +3 取其二補數得到 -3 的過程。 這定義也使得負數自動符合減法運算:只要再加上一個條件「溢位就忽略掉」。運算結果就只會在 `-4` ~ `+3` 之間循環。 例如運算 2 + (-3),在二進位的運算即對應 `010` + `101`,這其實在原本二進位的無號數定義中是 2 + 5 的意義。但因溢位就忽略掉造成的循環,我們發現 +5 的運算和 -3 兩者在運算上等價,也就是說,在這些運算之中: * +4 與 -4 效果相同 * +5 與 -3 效果相同 * +6 與 -2 效果相同 * +7 與 -1 效果相同 因此原本二進位無號數下半部的加法操作,可以直接照搬過來視為二進位有號數的減法操作。 補充資訊: [Bit-Level Representation of Two’s Complement Negation](http://csapp.cs.cmu.edu/3e/waside/waside-tneg.pdf) * 延伸閱讀 * [N1256 6.2.6.2](http://port70.net/~nsz/c/c99/n1256.html#6.2.6.2) p1~p2 * [C Defect Report #069](http://www.open-std.org/jtc1/sc22/wg14/docs/rr/dr_069.html) ![](https://i.imgur.com/H33tREX.png) 不是所有的位元組合都能表示合理的數字,存取某些位元組合在特定機器上可能會造成嚴重錯誤,此種組合稱作陷阱表示法 (trap representation)。除非使用位元運算或是違反標準其他規定 (如溢位),一般的運算不可能產生陷阱表示法。 C 語言標準明確允許實作自行決定在以下兩種狀況下是否是陷阱表示法: * 型態為有號整數且正負號及值位元為特定組合時 (三種格式各有一特殊組合) * 填充位元為某些組合時 :notes: [N1256 註腳# 44, 45](http://port70.net/~nsz/c/c99/n1256.html#note44) ![](https://i.imgur.com/DGJUVgk.png) 位元運算會忽略填充位元,因此(等級不低於 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` 不可能有陷阱表示法,堪稱是最安全的整數型態。實作可能不提供這些型態,不過一旦提供,即保證符合性質。 :notes: [N1256 7.18.1.1](http://port70.net/~nsz/c/c99/n1256.html#7.18.1.1) p1~p3 ![](https://i.imgur.com/HAhmxxQ.png) 有號數 x 到無號數 (U 結尾) 映射機制:非負數不變為 x,負數轉換為大的正數 (x + 2^w^,最靠近 0 的負數映射最大,最小的負數被映射為剛好在二補數表達之外的無符號數)。 * 例如 w = 4,二補數能表示的有號數範圍是 -8 [`1000`] ~ 7 [`0111`] ![](https://i.imgur.com/G2AXbpz.png) 在有號整數上都可能產生陷阱表示法 補充資訊: [Writing TMin in C](http://csapp.cs.cmu.edu/3e/waside/waside-tmin.pdf) * Figure 1 列出 ISO C90 和 ISO C99 對於資料型態定義的落差 * 注意 Implications ![](https://i.imgur.com/7YvR10S.png) 延伸閱讀: [Signed and Unsigned Numbers](https://chi_gitbook.gitbooks.io/personal-note/content/signed_and_unsigned_numbers.html) 在 [Whirlwind Tour of ARM Assembly](http://www.coranac.com/tonc/text/asm.htm) 指出,若 n 是有號 32-bit 整數,那麼 `n >> 31` 相當於 `n >= 0 ? 0 : -1` :-1: [bitwise left shift operation invokes Undefined Behaviour when the left side operand has negative value](https://stackoverflow.com/questions/3784996/why-does-left-shift-operation-invoke-undefined-behaviour-when-the-left-side-opera) :-1: [Weird behavior of right shift operator (1 >> 32) ](https://stackoverflow.com/questions/3394259/weird-behavior-of-right-shift-operator-1-32/3394302#3394302) 若 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 補數運算的值 ![](https://i.imgur.com/cWiCbnq.png) 例如: unsigned int to unsigned short :::info [第二部分錄影](https://youtu.be/cGjjDea7i8g) / [slides](https://www.cs.cmu.edu/~213/lectures/03-bits-ints-part2.pdf) 對應 CS:APP3e 的第 2 章: 2.3 整數運算 (==Page 60==) ::: 補充資訊: [More on Boolean Algebra and Boolean Rings](http://csapp.cs.cmu.edu/3e/waside/waside-boolean.pdf) * Properties of Boolean Algebras and Rings * epresenting and Manipulating Sets ![](https://i.imgur.com/qZ7RrmX.png) 用 XOR 檢查加法後是否有溢位 ```Clike long a, b, x; x = a + b; if ((x ^ a) >= 0 || (x ^ b) >= 0) ... ``` 檢查是否有加法導致的溢位: 1. 兩個正數相加變成負數表示溢位 2. 兩個負數相加變成正數也表示溢位 除了這兩者外沒有其它情況。綜合上述的條件,可簡化成:兩數相加後的正負號和原本兩者都不同 :notes: 溢位 採用二補數系統,最高 bit 作為是 sign bit,XOR 剛好可滿足簡化的條件,其它 bit 無關緊要,運算完看 sign bit 即可。 ![](https://i.imgur.com/6XFAwdJ.png) ![](https://i.imgur.com/ssCvkvg.png) 延伸閱讀: [C 語言的整數溢位問題](https://coolshell.cn/articles/11466.html) ==資訊安全== ![](https://i.imgur.com/sACQGVw.png) ![](https://i.imgur.com/R9AseEa.png) 一補數具有兩個 0 (+0、-0),加法器在做減法時,常需要一個額外的步驟,做端回進位。二補數即可避免這問題,因此無論是程式語言的整數表示或加法器的實作,幾乎皆採用二補數表示法。 ![](https://i.imgur.com/Qbptkxr.png) 在運算表達中,倘若其中一個為有號型態 (signed),編譯器會 implictly 將有號轉為無號運算。 * `-1 < 0U` 為 False * `-2147483647 - 1` (轉換為無號數相當於 2^32^)`== 2147483648U` 為 True 這種轉換帶來的錯誤有時很難發現,避免的方法是不濫用無號數。 :warning: Don't use unsigned without understanding implications * Easy to make mistakes ```C for (unsigned i= cnt - 2; i >= 0; i--) a[i] += a[i+1]; ``` * Can be very subtle ```C #define DELTA sizeof(int) for (int i= CNT; i - DELTA >= 0; i-= DELTA) ``` :+1: Counting Down with Unsigned * Proper way to use unsigned as loop index ```C 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 :notes: UMax * 最好改為: ```C 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^15^ + 1 (-32767) 到 2^15^ - 1 (32767) 之間的整數,16 位元已足夠 * 這也是為何 int 不一定是 32 位元 * [int_least32_t 和 int_fast32_t](https://en.cppreference.com/w/c/types/integer) (C99 開始引入的 fixed width integer types) 可保證存下至少 -2^31^ + 1 到 2^31^ - 1 之間的整數 * 由於不一定是沒有陷阱表示法的二補數,所以保證範圍的下限不是 -2^31^,而是 ==-2^31^ + 1== ![](https://i.imgur.com/IvCMbjE.png) bi-endianness (沒打錯,是 ==bi==,而非 "big") * 為了提高應用場域的效能和相容性,許多硬體架構如 Power, MIPS, ARM, 可透過特定的切換,支援 big, little 這兩種 byte-order ![](https://i.imgur.com/y19ZavM.png) 宋代學者趙與時在《賓退錄》說:「讀諸葛孔明《出師表》而不墮淚者,其人必不忠」,台灣人宅色夫在「進階電腦系統理論與實作」說:「讀 CS:APP 而不墮淚者,其人必不智」 :::warning 終於知道為何我們研究生追求達到 CMU 大學部二年級程度是多麽偉大的目標吧? ::: - [x] 練習題 2.30: `tadd_ok` (==Page 65==) ```C #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 的運算談浮點數](https://hackmd.io/s/ryOLwrVtz) * 對應 [CS:APP 3/e](http://csapp.cs.cmu.edu/) 的 **2.3.6** (==Page 70-74==), **2.4.5** (==Page 85-87==) * [使用浮點數最最基本的觀念](http://blog.dcview.com/article.php?a=Az0HYgNrBDU%3D) * Floating Point :::info [錄影](https://www.youtube.com/watch?v=cvE39UfP74Q) / [slides](https://www.cs.cmu.edu/~213/lectures/04-float.pdf) 對應 CS:APP3e 的第 2 章: 2.4.2 IEEE 浮點數表示 (==Page 78==), 2.4.5 浮點運算 (==Page 85==) ::: ![](https://i.imgur.com/vVlrGh6.png) ![](https://i.imgur.com/W0DbTqk.png) 3 種浮點型態 * denormalized * normalized * special ![](https://i.imgur.com/dgPdVWN.png) "Normalized" Values When: exp≠ 000...0 and exp≠ 111...1 ![](https://i.imgur.com/xFwkgOc.png) Denormalized Values Condition: exp = 000...0 Exponent value: E= 1 –Bias (instead of exp–Bias) Special Values Condition: exp= 111...1 ![](https://i.imgur.com/YQNgw5O.png) ![](https://i.imgur.com/nTLHd0I.png) ![](https://i.imgur.com/g6FFr7R.png) ![](https://i.imgur.com/1glL5eZ.png) ![](https://i.imgur.com/3MK7EYs.png) * [阿貝爾群也稱為可交換群 (commutative group)](https://ccjou.wordpress.com/2011/09/16/%E7%B7%9A%E6%80%A7%E4%BB%A3%E6%95%B8%E8%A3%A1%E7%9A%84%E4%BB%A3%E6%95%B8%E7%B5%90%E6%A7%8B/) ![](https://i.imgur.com/w5ghZNH.png) IEEE 754 浮點數值的比較,需要考慮到 sign + magnitude,實際操作類似以下: ```Clike #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==) > [參考解](https://hackmd.io/s/ryrcmhjOM) - [ ] [2018q1 第 2 週測驗題](https://hackmd.io/s/SJO5LN9_M) > [參考解](https://hackmd.io/s/BkM4w2Gaf) - [ ] [2018q1 第 3 週測驗題](https://hackmd.io/s/SknkEfVFf) > [參考解](https://hackmd.io/s/r1mnwM5aG) ###### tags: `cs:app`, `csapp`