2018q1 Homework2 (accessment) ================ contributed by <`AliennCheng`> ###### tags: `syshw` # 測驗題重作及解析 ## 第 1 週測驗題 測驗 `3` ### 原始題目 在 C 程式中，表達式 `1 << 2 + 3 << 4` 求值後為何？ `(a)` 512 `(b)` 16 `(c)` 26 `(d)` 52 `(e)` 25 :::info 延伸問題: * 在 C 語言規格書中，找出對應運算子優先權的描述並嘗試解讀 ::: ### 心路歷程 之所以選擇這題做 review ，純粹是因為自一開始學程式以來，從來沒有把 C 語言規格書打開來細讀過，因此想藉這次機會好好讀一次規格書，希望這次的經驗也可以讓以後遇到問題時，即時地想到：「啊，我該去翻翻規格書！」 重作這題很顯然是要直接從延伸問題下手，再回到原本的問題重新思考，因此我第一步就是去搜尋真正的「 C 語言規格書」。 ### 搜尋 ==C 語言規格書== 首先，我在[維基百科的 C 語言項目](https://zh.wikipedia.org/wiki/C%E8%AF%AD%E8%A8%80)當中，發現最新的規格是 [ISO/IEC 9899:2011 (簡稱 ==C11==)](http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1570.pdf)，但是在老師的共筆[你所不知道的 C 語言: 開發工具和規格標準](https://hackmd.io/s/HJFyt37Mx)當中，採用的卻是 [ISO/IEC 9899 (簡稱 ==C99==)](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf)，由於目前還沒有時間研讀該共筆，因此在這裡留個 `TODO`，而以下內容暫時以 C99 作為標準。 :::info TODO: 研讀「[你所不知道的 C 語言: 開發工具和規格標準](https://hackmd.io/s/HJFyt37Mx)」，探討為甚麼老師採用 C99 規格而非 C11。 ::: :::danger 純粹只是從 C99 開始，這是 C 和 C++ 兩個程式語言分道揚鑣的關鍵時間點 (1999 年)，系列講座有包含 C11 :notes: jserv ::: >感謝老師解答疑惑!![name=AliennCheng] ### 閱讀規格書 為求內容完整，也恰巧規格書中的內容連貫，我決定把 `+` 和 `<<` 的內容全數翻譯在下方，因為這是我第一次嘗試翻譯，若有用詞不精準之處也麻煩看到的大大幫忙糾正。 #### 6.5.6 Additive operators 加法運算子 ##### 語法 ``` 加法運算式: 乘法運算式 加法運算式 + 乘法運算式 加法運算式 - 乘法運算式 ``` ##### 限制 * 在加法中，兩個運算元需「皆為算術型態 (arithmetic type)」，或是「一個為指向物件的指標，另一個為整數型態」 * 在減法中，需滿足下列條件中至少一項 * 兩個運算元皆為算術型態 * 兩個運算元皆為指向相容物件（無論是否為合格版本）的指標 :::info 原文如下，當中的 qualified 我不確定怎麼翻比較好 both operands are pointers to qualified or unqualified versions of compatible object types ::: * 左運算元為指向物件型態的指標，右運算元為整數型態 ##### 語意 * 若兩運算元皆為算術型態，則以正常的算術法則處理 * `+`的運算結果為兩運算元之和 * `-`的運算結果為首運算元減去次運算元所得之差 * 基於這兩個運算子的目的，一個「指向非陣列元素的指標」的行為，會等同於「一個指向『長度為一且其元素型態即為指標所指之物件型態的陣列』其首項元素的指標」 * 當一個具有整數型態的運算式被指標所加或減時，其結果為該指標運算元的型態。若該指標運算元指向陣列物件的其中一個元素，且該陣列足夠大時，其運算結果即為指向「自原指標所指向之索引處偏移該整數量後之索引」的指標。換句話說，若運算式 `P` 指向一個陣列物件的第 *i* 個元素，且給定變數 `N` 有值 *n* ，則運算式 `(P)+N` 及 `N+(P)` 指向該陣列的第 *i*+*n* 個元素，而運算式 `(P)-N` 指向該陣列的第 *i*-*n* 個元素（此時會自動假設其存在）。除此之外，若運算式 `P` 指向一個陣列物件的最後一個元素，則運算式 `(P)+1` 會指向該陣列物件最後一個元素的後面一個位址，而若運算式 `Q` 指向一個陣列物件最後一個元素的後面一個位址，則運算式 `(Q)-1` 會指向該陣列的最後一個位址。當運算元及運算結果的指標皆指向某一陣列物件當中的元素，或是最後一個元素的後一個位址時，該運算並不會產生溢位 (overflow)，否則，該行為為未定義。如果運算結果指向陣列物件最後一個元素的後一個位址時，它不應該被 `*` 運算子所操作。 * 當兩個指標相減時，該兩個指標需指向相同的陣列物件或該陣列最後一個元素的後一位。運算結果亦為指標，其指向的位置在該陣列的索引，即為兩運算元指標所指之處在該陣列的對應索引之差。這個運算結果的大小的累加是有所定義的，且它的型態（即有號整數型態）在標頭檔 `<stddef.h>` 中被定義為 `ptrdiff_t`。若其結果指標在對應物件的型態中是不可表現的，則該行為不被定義。換句話說，在某一陣列物件中，若運算式 `P` 指向第 *i* 個元素，而運算式 `Q` 指向第 *j* 個元素，則運算式 `(P)-(Q)` 的結果型態為 `ptrdiff_t`，其內容為 *i*-*j*。更進一步地說，若運算式 `P` 指向某陣列物件的元素或是其最後一個元素的後一位址，而運算式 `Q` 指向該陣列物件的最後一個元素，則運算式 `((Q)+1)-(P)` 、`((Q)-(P))+1` 和 `((P)-((Q)+1))` 皆具有相同值，此時若 `P` 指向該陣列物件的後一位址的話，則上述三運算式之結果皆為零（儘管運算式 `(Q)+` 並不指向陣列物件中的元素）。 * **範例** 在陣列長度為變數的情況下，指標算數仍是被完全定義的 (well-defined)。 ```=clike { int n = 4, m = 3; int a[n][m]; int (*p)[m] = a; // p == &a[0] p += 1; // p == &a[1] (*p)[2] = 99; // a[1][2] == 99 n = p - a; // n == 1 } ``` * 上述範例中，如果陣列 `a` 被定義為已知的固定長度，且指標 `p` 被定義為指向一個已知為固定大小的陣列（即指向 `a`），則其結果仍會和上述相同。 #### 6.5.7 Bitwise shift operators 位移運算子 ##### 語法 位移運算式: 加法運算式 位移運算式 << 加法運算式 位移運算式 >> 加法運算式 ##### 限制 運算元需為整數型態 ##### 語意 * 運算元會提升 (promotion) 整數個位元。運算結果的型態和被提升位元後的左運算元的型態相同。若右運算元的值為負值或是大於等於左運算元可供提升的寬度時，則運算行為未被定義。 * 運算 `E1 << E2` 的結果即為 `E1` 被向左移了 `E2` 個位元 (bit positions)，此時被騰出的空間將被補上零值。在這個運算中，如果 `E1` 具有無號型態，則運算的結果即為 E1×2^E2^ 的結果再除以其對應型態可表示之最大值所得之餘數。如果 `E1` 具有有號型態且不為零值，且運算 E1×2^E2^ 的結果在其對應型態中為可表示的，則該表示值即為結果，否則該運算為未定義。 * 運算 `E1 >> E2` 的結果即為 `E1` 被向右移了 `E2` 個位元。在這個運算中，如果 `E1` 具有無號型態或是具有有號型態且非負時，運算結果的值即為 E1/2^E2^。而若 `E1` 具有有號型態且為負值時，其運算結果為實作定義 (implementation-defined)。 > 翻譯時我並不瞭解甚麼是 implementation-defined，經過一番查詢才知道這代表該運算式或數值等等是「由實作品自行定義」，而實作品通常指的是編譯器。[name=AliennCheng] ### 問題答案與心得 顯然我多費了一大段功夫，但翻到一半發現答案就在眼前時也只是想說「頭都洗下去了就把它洗完吧...」 本題答案就在 Bitwise shift operations 的語法處，其中標明加法運算式包含於位移運算式，也就是說==加法運算的優先權是高於位移運算的==，並且左邊的運算優先於右邊的運算，因此本題結果如下 :::success 1 << 2 + 3 << 4 = 1 << ( 2 + 3 ) << 4 = 512 ::: :::info 但問題來了，為甚麼當初設計時會把加減法運算的權重設計在位移運算之上呢？是因為加減法的運算成本比位移運算低嗎？我至今仍然想不明白。 ::: --- ## 第 1 週測驗題 測驗 `4` ### 原始題目 考慮某些硬體平台執行乘法的時間較長，我們會以 `(x << 5) - (x)` 取代 `*` 31，那麼 `*` (-6) 該如何用 shift 搭配 add/sub 實作呢？ `(a)` 2 個 shift 搭配 0 個 add/sub `(b)` 2 個 shift 搭配 2 個 add/sub `(c)` 2 個 shift 搭配 1 個 add/sub `(d)` 1 個 shift 搭配 1 個 add/sub `(e)` 0 個 shift 搭配 2 個 add/sub :::info 延伸問題: * 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？ ::: ### 問題解答 當我們試圖將某數 `x` 乘以 (-6) 時，可以做以下推導 ``` x * (-6) = x * ( 2 - 8 ) = x * 2 - x * 8 ``` 又 `x * 2` 等價於將 x 左移一位，而 `x * 8` 等價於將 x 左移三位，也就是說，可以用兩個位移運算加上一個減法運算得到 `x * ( -6 )` 的結果。 ### 延伸問題思考 由上面兩個例子可以發現，試圖將 `x` 乘以一個數取代成位移和加減法的組合時，需要先將該數化為 2 的次方數的運算式，也就是 2^a1^ +- 2^a2^ +- ... +- 2^an^。 因此本延伸問題等價於「是否存在最小值 k 使得表示式 2^a1^ +- 2^a2^ +- ... +- 2^ak^ 足以表示所有整數，a1, a2, ... , ak 為任意相異整數」。 我的第一直覺猜測結果是否定的，但是不知道該如何開始證明，因此我下面先暴力窮舉一番，列出「乘以 30 以內的正奇數所需要的運算數量」，看看能不能觀察出甚麼端倪。選擇用奇數純粹是因為偶數必是某個數多位移一位而已，因此若取奇數時有唯一最小值，則取偶數必存在唯一最小值。 ### 舉例 | | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 | 21 | 23 | 25 | 27 | 29 | | ----- | - | - | - | - | -- | -- | -- | -- | -- | -- | -- | -- | -- | -- | | shift | 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | |add/sub| 1 | 1 | 1 | 1 | 2 | 2 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | ### 觀察 出乎意料地，竟然不是 1/1 就是 2/2 ，在過程中我只是用前一個數字或是最接近的 2 的次方，搭配之前出現過的較小數如 3 , 5 等湊出下一個數字而已，其實這過程就有點數學歸納法的味道，但我還是掌握不住規律，因此我決定在 32 和 64 之間的奇數再試一次，這次直接列出計算式觀察看看。 ### 再舉例一次 ``` 33 = 32 + 1; 35 = 32 + 2 + 1; 37 = 32 + 4 + 1; 39 = 32 + 8 - 1; 41 = 32 + 8 + 1; 43 = 32 + 8 + 2 + 1; 45 = 32 + 8 + 4 + 1 = 32 + 16 - 4 + 1; 47 = 32 + 16 - 1; ``` ### 再觀察 不用算到 63 我心裡就有個底了，可以發現，當 2 的次方越來越大時，間隔中所包含的數更多，儘管 2 的次方數的數量跟著增加，但要僅透過該 2 次方或下一個 2 次方，配合 1, 3, 5 這種只用一次 shift 的較小數組合出所有數的難度也隨之增加，在 41 之前都可以用 3 個 2 的次方向（也就是只靠最接近的 2 的次方配合 1, 3, 5 等只消耗一次 shift 的數）湊出，但 43, 45 就超過 2 shift 加上 2 add/sub 的限制了。 從這裡我觀察到，是不是 2 的次方項和其下一個次方項的幾何平均左右的數會造成這樣的 shift 數突破呢？下面試著測試看看... ``` 4 -> 8 之間 => 5.66 => 附近奇數皆可在 1 shift & 1 add/sub 內完成 8 -> 16 之間 => 11.31 => 可找到 11 = 8 + 2 + 1 16 -> 32 之間 => 22.63 => 附近奇數皆可在 2 shift & 2 add/sub 內完成 32 -> 64 之間 => 45.25 => 可找到 45 = 32 + 8 + 4 + 1 64 -> 128 之間 => 90.51 => 附近奇數皆可在 3 shift & 3 add/sub 內完成 128 -> 256 之間 => 181.02 => 可找到 181 = 128 + 32 + 16 + 4 + 1 這次沿著之前的規律跳一項看看 512 -> 1024 之間 => 724.08 => 可找到 725 = 512 + 256 - 32 - 8 - 2 - 1 ... ``` 若考慮偶數時就只是多一個 shift （多了把那個 1 轉成 2 的 shift），再考慮負數也只是正負號互換，因此測試應該到這邊可以結束了。 :::success 好像成功試出會突破 shift 次數的規律來，也就是每當「 2 的奇數次方項和其更高一次方的數，這兩數的幾何平均」附近，會有 shift & add/sub 次數的突破。也就是不存在最小次數的 shift & add/sub 可取代乘法。 :::info 但目前還是不瞭解為甚麼有這樣的規律，我短時間內也想不到嚴謹的證明... ::: > 其實換個角度想，如果有這種方法的話現在的電腦何必需要乘法器呢 xD [name=AliennCheng] > 編譯器最佳化時，可能會套用上述「乘以某常數」的模式去改寫程式碼，請利用 clang/gcc 的 `-Ofast` 和 `-S` 的選項觀察輸出的組合語言 [name="jserv"] --- ## 第 3 週測驗題 測驗 `2` ### 原始題目 考慮到下方函式 `shift_right_arith` 和 `shift_right_logical` 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，而位移量 `k` 的有效範圍在 0 到 `w - 1`。 ```=clike #include <stdio.h> int shift_right_arith(int x, int k) { int xsrl = (unsigned) x >> k; int w = sizeof(int) << P1; int mask = (int) -1 << (P2); if (x < 0) return xsrl P3 mask; return xsrl; } unsigned shift_right_logical(unsigned x, int k) { unsigned xsra = (int) x >> k; int w = sizeof(int) << P4; int mask = (int) -1 << (P5); return xsra P6 P7; } ``` ### 解題脈絡 由於前兩題已經大量使用 shift 的概念了，這部分就只有[算數 (arithmetic) 右移](https://en.wikipedia.org/wiki/Arithmetic_shift)和[邏輯 (logical) 右移](https://en.wikipedia.org/wiki/Logical_shift)兩者的差別需要特別釐清，這篇[邏輯移位和算數移位有甚麼區別？](https://edwardluo.wordpress.com/2015/04/08/%E9%80%BB%E8%BE%91%E7%A7%BB%E4%BD%8D%E5%92%8C%E7%AE%97%E6%9C%AF%E7%A7%BB%E4%BD%8D%E6%9C%89%E4%BB%80%E4%B9%88%E5%8C%BA%E5%88%AB%EF%BC%9F/)講的還滿仔細，有需要的可以參考，在此就不贅述。 回到原題，以下就分別對給定的算術及邏輯右移函式，重新梳理一次脈絡，同時把挖空的地方補上。 #### 算數右移 首先來探討一下原題目的這個函式 ```=clike= #include <stdio.h> int shift_right_arith(int x, int k) { int xsrl = (unsigned) x >> k; int w = sizeof(int) << P1; int mask = (int) -1 << (P2); if (x < 0) return xsrl P3 mask; return xsrl; } ``` 已知我們要把輸入 x （型態為 int，也就是 8 byte）右移 k 位。 第三行這邊 `>>` 的行為恰巧在上面翻譯過： ``` 運算 E1 >> E2 的結果即為 E1 被向右移了 E2 個位元。 在這個運算中，如果 E1 具有無號型態或是具有有號型態且非負時，運算結果的值即為 E1/(2^E2)。 而若 E1 具有有號型態且為負值時，其運算結果為實作定義 (implementation-defined)。 ``` 換句話說，若 x 本來就是非負值，則 xsrl 的值即是 x 原值除以 2 的 k 次方。然而，若 x 為負值時，為了保證函式運作的一致性，這裡先取了 cast 將其暫時化成無號的型態，也就是原本為負的 x 最左 bit 原是 1，但在第三行執行後暫時在左邊補上了 k 個 0。在這個時候，如果 x 原為非負值的話， xsrl 其實已經是所求了，但若 x 原為負值則還需要再經過修正。 :::info 經過上面的深入分析，這個函式的 4, 5 行是不是應該包含在 `if` 裡面執行起來比較有效率呢？又或者採用的 prediction 方式不同，在某種時候這樣的寫法會更好？ ::: 接下來就是要把 x 原為負時，經過第三行後左邊補的那 k 個 0 改成 1 了。 首先，我們只知道最左邊有 k 個 1，但不知道右邊有幾個被保留下來的 bit，又因為被保留 bit 數量和 k 加起來會等於對應型態的 bit length（在這裡是 `int`），因此我們可以藉由計算總共有幾個 bit，來推算右邊需要保留幾個 bit，進而在左邊補上 1。 概念講完了，實作上第四行就是要取得 `int` 的 length，但因為 `sizeof()` 這個函式回傳的是 byte 數，因此要乘以 8 才是 bit 數，經過上面那一番翻譯之後這 shift 的行為很熟了，因此 `P1` 處便是 `log(8) = 3`。接著第五行要做一個左邊為 k 個 1 的遮罩，將剛剛補錯的 0 修正回來，又因為左移時右邊必補 0，因此拿 `int` 型態的 -1 作為媒介最直接，因為它在 bit 的觀點上是個全為 1 的值，將此值左移直到原本的最右位元移到左邊數來第 k 位便是我們所需要的遮罩，而這個位移量即是 `P2 = length - k = w - k`。最後，第七行的位置要將此遮罩蓋在 `xsrl` 上，因為遮罩的右側全為 0 不影響保留下來的值，因此我們使用 [bitwise operation](https://en.wikipedia.org/wiki/Bitwise_operation) 當中的 `|` 運算將 `xsrl` 左邊的 0 用遮罩左邊的 1 取代，也就是 `P3 = |`。 #### 邏輯右移 接著來探討下面這個函式 ```=clike= unsigned shift_right_logical(unsigned x, int k) { unsigned xsra = (int) x >> k; int w = sizeof(int) << P4; int mask = (int) -1 << (P5); return xsra P6 P7; } ``` 邏輯右移的部分就更直覺了，就是將 x 的 bit 型態往右移 k 位，騰出來的位置全補 0。特別需要注意的是，討論邏輯右移時我們希望這個行為是在掌握之中，因此輸入 x 以及回傳值皆為 unsigned 型態，以符合 `>>` 運算的要求。 可以發現這個函式是特別設計來考試用的函式，實際上第二行不需要 cast，執行完就可以回傳了。但這邊特別將 x 換成 int 的型態，也就是說這個時候我們對於左邊 k 位是未定義的，需要一個遮罩將左邊全部蓋成 0。 因此同樣道理，`P4 = 3` 先取得 `int` 的長度，`P5 = w - k` 做一個左邊 k 位為 1 其餘位為 0 的遮罩。但不同的地方在這次要把 `xsra` 的左邊用 0 取代，因此在這裡把遮罩取補數，即 `P7 = ~mask`，使其成為左邊 k 位為 0，右邊全為 1 的狀態，再利用 `P6 = &` 運算將 0 補上，且遮罩右邊全為 1 不影響 `xsra` 所保留的值。 --- :::info 延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制 ::: [x86_64](https://zh.wikipedia.org/wiki/X86-64) 是 Intel 以及 AMD 處理器所採用架構之一，[Aarch32/Aarch64](https://en.wikipedia.org/wiki/ARM_architecture#AArch64_features) 又稱 ARMv8 是 ARM 的架構之一，因為我本身也不夠了解，在這裡就不贅述。 :::info TODO: 詳閱[成大 wiki 中對 ARMv8 的介紹](http://wiki.csie.ncku.edu.tw/embedded/ARMv8)，並進一步和現今電腦處理器主流採用的 x86_64 比較 ::: x86 的部分，可以從 intel 官方找到他們自己的[開發手冊](https://software.intel.com/en-us/articles/intel-sdm)，但他們還分好幾冊實在有夠複雜，這部分我還沒搞清楚。 而 ARMv8 的部分，可以找到他們自己的[規格書](http://infocenter.arm.com/help/topic/com.arm.doc.den0024a/DEN0024A_v8_architecture_PG.pdf)，這部分比較易讀，有關的敘述如下 ``` Logical Shift Right (LSR). The LSR instruction performs division by a power of 2. Arithmetic Shift Right (ASR). The ASR instruction performs division by a power of 2, preserving the sign bit. ``` ![ARMv8_shift](https://i.imgur.com/UsLgrzL.jpg) ``` The register that is specified for a shift can be 32-bit or 64-bit. The amount to be shifted can be specified either as an immediate, that is up to register size minus one, or by a register where the value is taken only from the bottom five (modulo-32) or six (modulo-64) bits. ``` :::info TODO: 簡單分析兩架構對於算數右移及邏輯右移的指令有何特色，並比較其區別。 ::: # 閱讀 [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) 的啟發 :::info TODO: 補上心得 ::: # 學習筆記 :::info TODO: 未來有時間會慢慢補齊[你所不知道的 C 語言](http://hackfoldr.org/dykc/)以及 CS:APP 的內容，再陸續將自己的學習筆記補在這裡 :::