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

延伸問題:

• 在 C 語言規格書中，找出對應運算子優先權的描述並嘗試解讀

心路歷程

之所以選擇這題做 review ，純粹是因為自一開始學程式以來，從來沒有把 C 語言規格書打開來細讀過，因此想藉這次機會好好讀一次規格書，希望這次的經驗也可以讓以後遇到問題時，即時地想到：「啊，我該去翻翻規格書！」

重作這題很顯然是要直接從延伸問題下手，再回到原本的問題重新思考，因此我第一步就是去搜尋真正的「 C 語言規格書」。

搜尋 C 語言規格書

首先，我在維基百科的 C 語言項目當中，發現最新的規格是 ISO/IEC 9899:2011 (簡稱 ==C11==)，但是在老師的共筆你所不知道的 C 語言: 開發工具和規格標準當中，採用的卻是 ISO/IEC 9899 (簡稱 ==C99==)，由於目前還沒有時間研讀該共筆，因此在這裡留個 TODO，而以下內容暫時以 C99 作為標準。

TODO: 研讀「你所不知道的 C 語言: 開發工具和規格標準」，探討為甚麼老師採用 C99 規格而非 C11。

純粹只是從 C99 開始，這是 C 和 C++ 兩個程式語言分道揚鑣的關鍵時間點 (1999 年)，系列講座有包含 C11

jserv

感謝老師解答疑惑!!AliennCheng

閱讀規格書

為求內容完整，也恰巧規格書中的內容連貫，我決定把 + 和 << 的內容全數翻譯在下方，因為這是我第一次嘗試翻譯，若有用詞不精準之處也麻煩看到的大大幫忙糾正。

6.5.6 Additive operators 加法運算子

語法

加法運算式:
    乘法運算式
    加法運算式 + 乘法運算式
    加法運算式 - 乘法運算式

限制

• 在加法中，兩個運算元需「皆為算術型態 (arithmetic type)」，或是「一個為指向物件的指標，另一個為整數型態」
• 在減法中，需滿足下列條件中至少一項
  • 兩個運算元皆為算術型態
  • 兩個運算元皆為指向相容物件（無論是否為合格版本）的指標

  原文如下，當中的 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)。

{
    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，經過一番查詢才知道這代表該運算式或數值等等是「由實作品自行定義」，而實作品通常指的是編譯器。AliennCheng

問題答案與心得

顯然我多費了一大段功夫，但翻到一半發現答案就在眼前時也只是想說「頭都洗下去了就把它洗完吧…」
本題答案就在 Bitwise shift operations 的語法處，其中標明加法運算式包含於位移運算式，也就是說加法運算的優先權是高於位移運算的，並且左邊的運算優先於右邊的運算，因此本題結果如下

1 << 2 + 3 << 4 = 1 << ( 2 + 3 ) << 4 = 512

但問題來了，為甚麼當初設計時會把加減法運算的權重設計在位移運算之上呢？是因為加減法的運算成本比位移運算低嗎？我至今仍然想不明白。

---

第 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

延伸問題:

• 乘以某個整數的運算，如果拆解為 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），再考慮負數也只是正負號互換，因此測試應該到這邊可以結束了。

好像成功試出會突破 shift 次數的規律來，也就是每當「 2 的奇數次方項和其更高一次方的數，這兩數的幾何平均」附近，會有 shift & add/sub 次數的突破。也就是不存在最小次數的 shift & add/sub 可取代乘法。

但目前還是不瞭解為甚麼有這樣的規律，我短時間內也想不到嚴謹的證明…

其實換個角度想，如果有這種方法的話現在的電腦何必需要乘法器呢 xD AliennCheng
編譯器最佳化時，可能會套用上述「乘以某常數」的模式去改寫程式碼，請利用 clang/gcc 的 -Ofast 和 -S 的選項觀察輸出的組合語言 "jserv"

---

第 3 週測驗題 測驗 2

原始題目

考慮到下方函式 shift_right_arith 和 shift_right_logical 分別表示算術右移和邏輯右移，請嘗試補完程式碼。可由 sizeof(int) * 8 得知整數型態 int 的位元數 w，而位移量 k 的有效範圍在 0 到 w - 1。

#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) 右移和邏輯 (logical) 右移兩者的差別需要特別釐清，這篇邏輯移位和算數移位有甚麼區別？講的還滿仔細，有需要的可以參考，在此就不贅述。

回到原題，以下就分別對給定的算術及邏輯右移函式，重新梳理一次脈絡，同時把挖空的地方補上。

算數右移

首先來探討一下原題目的這個函式

#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 原為負值則還需要再經過修正。

經過上面的深入分析，這個函式的 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 當中的 | 運算將 xsrl 左邊的 0 用遮罩左邊的 1 取代，也就是 P3 = |。

邏輯右移

接著來探討下面這個函式

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 所保留的值。

---

延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制

x86_64 是 Intel 以及 AMD 處理器所採用架構之一，Aarch32/Aarch64 又稱 ARMv8 是 ARM 的架構之一，因為我本身也不夠了解，在這裡就不贅述。

TODO: 詳閱成大 wiki 中對 ARMv8 的介紹，並進一步和現今電腦處理器主流採用的 x86_64 比較

x86 的部分，可以從 intel 官方找到他們自己的開發手冊，但他們還分好幾冊實在有夠複雜，這部分我還沒搞清楚。
而 ARMv8 的部分，可以找到他們自己的規格書，這部分比較易讀，有關的敘述如下

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.

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.

TODO: 簡單分析兩架構對於算數右移及邏輯右移的指令有何特色，並比較其區別。

閱讀 因為自動飲料機而延畢的那一年 的啟發

TODO: 補上心得

學習筆記

TODO: 未來有時間會慢慢補齊你所不知道的 C 語言以及 CS:APP 的內容，再陸續將自己的學習筆記補在這裡