2018q1 Homework2 (assessment) === contributed by <`raygoah`> # 課前測驗參考解答 ## Week 1 ### 題目： 考慮以下整數乘法的實作程式碼: ```clike int mul(int n, int m) { int ret = 0; for (int c = 0; m; c++, m /= 2) if (!(m % 2 - 1)) OP return ret; } ``` ### 想法及思考 1. 一開始看到題目，可以知道此題是為了要做乘法 2. 看到在 `for` 迴圈中，每次都將 m / 2 ，同時將 c 的值加一，可以聯想到 `n << 1` 代表把 n 乘 2 乘一次，因此若寫成 `n << c` ，及代表要將 n 乘 2 乘 c 次 3. 而觀察到 `for` 迴圈中的 `if` ，猜測本題重點便是在於為什麼達成 `if` 的條件後要進行 OP ，這背後代表的意思，就是完成這題乘法的關鍵 ### 解題思緒 * 從 `if (!(m % 2 - 1)) OP` 中可以知道，只有在 m 為奇數時，OP 才會執行，而這代表著只有在 m 一開始就是奇數，第一次進迴圈的時候 OP 會被執行，此外還有在跳出迴圈前一次，m = 1 時，OP 會被執行 * 而從以上幾點來看，迴圈中每次將 m 除以 2，並將 c 加一的目的，便是要將 m 改寫成 $2^c$，但這樣會因為 m 是奇數時而無法順利表示，因此若要在 m 是奇數時表示成 $2^c+1$ 的話，便需要利用 m 是奇數時第一次進入 `for` 迴圈中，`if` 的條件式會成立，OP 會執行的這一點，即可以順利的將 m 表示成 $2^c+1$ * 而在了解了 m 是如何表示後，便可以了解此題想要做的，應該是要把 $n * m$ 改寫成以下兩種狀況 * m 為奇數時： $(n * 2^c) + (n * 1)$ * m 為偶數時： $n * 2^c$ * 而這時便可以利用 `<<` 的特性，每向左移一位元代表乘以二，以及結合上述的想法，便可以選出正確答案：OP 為 `(e)` ret += n << c; ### 延伸問題 #### 解釋為何乘法可運作？ - 如我在上方所提到，此題將乘數 m 改寫，依照 m 為奇或偶分別寫成 $2^c + 1$ 以及 $2^c$，因此整個乘法便會改寫成如下所示： * m 為奇數時： $(n * 2^c) + (n * 1)$ * m 為偶數時： $n * 2^c$ - 在將$n * m$ 改寫後，便可以利用 `<<`，寫成如題目的程式碼，順利的完成可運作的乘法程式 ### 參考 * `rwe0214` 在課堂上的講解 ## Week 2 ### 題目： ```clike typedef unsigned int float_bits; float_bits float_x0_5(float_bits f) { unsigned sig = f >> 31; unsigned rest = f & 0x7FFFFFFF; unsigned exp = f >> 23 & 0xFF; unsigned frac = f & 0x7FFFFF; /* NaN or INF */ if (exp == A0) return f; /* round to even. Last 2 bits of frac are considered: * 00 => 0 just >> 1 * 01 => 0 (round to even) just >> 1 * 10 => 1 just >> 1 * 11 => 1 + 1 (round to even) just >> 1 and plus 1 */ int addition = (frac & 0x3) == 0x3; /* Denormalized */ if (exp == 0) { frac >>= A1; frac += addition; /* Normalized to denormalized */ } else if (exp == 1) { rest >>= A2; rest += addition; exp = rest >> A3 & A4; frac = rest & 0x7FFFFF; /* Normalized */ } else { exp -= A5; } return sig << A6 | exp << 23 | frac; } ``` ### 想法及思考 * 看完題目可以知道，此題的 function 想要做的，是將以 IEEE 754 表示的 32 位元浮點數乘與 0.5 * 要先搞清楚 IEEE 754 的規則，當初就是沒有搞清楚，結果這幾題都錯很慘，念資工連這都不會，慚愧... * 主要要測驗的，是其中註解為 Denormalized 以及 Normalized 的部份，熟悉規則便可解決 * fraction 為 0 ~ 22 bits，exp 為 23 ~30 bits，sign bit 為第 31 bit ### 解題思緒 * 照著題目順序從 A0 看到 A6，雖然每一題的選項都很多，但只要知道 IEEE 754 的規則，要選出正確答案不難 * A0: ```clike /* NaN or INF */ if (exp == A0) return f; ``` * 可以看到註解清楚的告訴我們，這邊是要處理關於遇到 NaN 以及 INF 時該做什麼 * 這裡是決定當遇到這兩種情況時，就不用再乘 0.5，直接回傳原本的數字 * 因此考慮到 IEEE 754 對於 NaN 以及 INF 的定義，這兩種情況的 exp 值會是全為 1 ，因此要選擇一個全為 1 的答案，也就是 0xFF * A1: ```clike /* Denormalized */ if (exp == 0) { frac >>= A1; frac += addition; } ``` * A1 關係到的部份，是在遇到非規格化的值時，該做些什麼處理 * 這部份也是滿直觀的，因為非規格化的值，exp 為 0 ，因此在這裡不需要做什麼，只需要將 fraction 的部份乘上 0.5，也就是右移一次即可，所以 A1 選 1 * 而在 `frac += addition;` 的部份是用於做捨入的，採用 round to even 的方法，捨入的方法在 code 中的註解有詳細的介紹 * A2 A3 A4: ```clike /* Normalized to denormalized */ else if (exp == 1) { rest >>= A2; rest += addition; exp = rest >> A3 & A4; frac = rest & 0x7FFFFF; } ``` * 在這個 else if 中，需要填的是 A2 A3 以及 A4 * 而同樣的註解有說明，這部份所要做的是將規格化的數字在乘上 0.5 後，成為非規格化的數字時，所需要做的處理 * 這邊利用了在前面先把 sign bit 拿掉後得到的 rest，把 rest 先乘上 0.5，也就是右移一次，所以這裡 A2 和 A1 一樣，也是選 1 * 接著在 `rest += addition;` 的部份，同樣的也是做捨入 * 而在 `exp = rest >> A3 & A4;` 這裡，要從 rest 中把第 23 到第 31 bit 的數字取出，也就是只要留下 exp 的部份，因此需要先向右移位 23 次，再和 0x7FFFFFFF 做一次遮罩，便可以得到，因此 A3 為 23，而 A4 則是選擇 0x7FFFFFFF :::info 這邊不理解的一點是，對於 exp 為何不直接將其設為 0 因為在乘完 0.5 後，得到的答案會是非規格化的數字，而在 IEEE 754 中，只要是非規格化的數字，exp 都會是 0，那麼為何要選擇用 bitwise 的方式而非將 exp 直接設為 0 呢？ ::: :::warning 有猜測和質疑很好，那去寫程式驗證吧！ :notes: jserv ::: * A5 ```clike /* Normalized */ else { exp -= A5; } ``` * 在 A5 的部份，是關於規格化的數字乘上 0.5 後，還是規格化的數字時，所要做的處理 * 因為我們要做的是要將整個數乘上 0.5，也就是表示成 $(-1)^s * M * 2^E$ 時，E 的值必須要減一，因此我們將 exp 減 1，即可解決，A5 的答案為 1 * A6 ```clike return sig << A6 | exp << 23 | frac; ``` * 在最後要將上面得到的 sig, exp 以及 frac 合成一個資料型態為 unsigned int 的數字回傳，因此依照 IEEE 754 規定，sign bit 為第 32 個 bit，因此將 sig 向左移位 31 次，A6 選澤 31 ### 參考 * CS:APP 3/e ## Week 3 ### 題目： 考慮到下方函式 `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; } ``` ### 想法及思考 * 先了解算術右移以及邏輯右移兩者的不同 * 題目有兩點提示： 1. 可由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w` 2. 移位量 `k` 的有效範圍在 0 到 `w - 1` ### 解題思緒 * 首先先由算術右移的部份下手： * 算術右移的特點在於，右移完後會依照 sign bit 是多少，把空缺的 bits 補上，讓右移完成後的結果和原數正負號相同 ```clike 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; } ``` * `int xsrl = (unsigned) x >> k;` 首先將 x 右移 K 位 * `int w = sizeof(int) << P1;` 這邊可由提示中提到，由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，因此要乘上 8 就等同於向左移位 3 次，因此 P1 為 3 * `int mask = (int) -1 << (P2);` 在這裡 mask 為了要讓原本是小於 0 的數，在經過算術右移後得到的結果仍舊是負數，因此之後要對從右邊數來 k 個 bits 做遮罩，所以在這邊要將 -1 向左移 (w-k) 次，因此 P2 選擇 `w-k` * 在有關 P3 的部份，接續了 P2，也就是為了要讓原本是小於 0 的數，在經過算術右移後得到的結果仍舊是負數，因此要把 xsl 和 mask 的每個 bit 做邏輯運算的 'or' ，把右邊數來 k 個 bits 全部設為 1 ，因此在這邊 P3 要選 `|` * 接著是邏輯右移的部份 * 邏輯右移與算術右移不同，在右移後，不管原本數字是正或是負，左邊補上的都是 0 ，因此可能會有原本是負數但經過算術右移後得到正數的結果 ```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; } ``` * P4 的地方和 P1 一樣，`sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w`，因此 P4 為 3 * P5 也是和 P2 的概念一樣，只是之後遮罩的作法不同，但這邊也是為了讓 mask 從右數來 k 個 bits 皆為 1 其他位元皆為 0，因此在這裡 P5 也是選擇 w-k * P6 P7 的部份是邏輯右移與算術右移最重要的區別，在邏輯右移中要讓右移後從左邊補上的 bits 全部為 0 ，因此要先將 mask 做一次邏輯運算的 `not` ，讓 mask 從原本的右邊數來 k 個 bits 皆為 1 其他位元皆為 0 ，變成從右數來 k 個 bits 皆為 0 其他位元皆為 1，接著和 xsrl 做 & ，確認右邊數來 k 個 bits 全部為 0 ，而左邊數來 k 個 bits 留下移位後要的數字，得到最後的結果，因此 P6 為 `&` 而 P7 為 `~mask` ## 延伸題目 * 題目：在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制 * x86_64： * 邏輯移位：shr 以及 shl * 用法: `shr src, dest ` 將 dest 向左移位 src 個 bits * 範例： ``` movw $ff00,%ax # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256) shrw $3,%ax # ax=0001.1111.1110.0000 (0x1fe0, signed and unsigned 8160) # (logical shifting unsigned numbers right by 3 # is like integer division by 8) shlw $1,%ax # ax=0011.1111.1100.0000 (0x3fc0, signed and unsigned 16320) # (logical shifting unsigned numbers left by 1 # is like multiplication by 2) ``` * shr 為向右移位，shl 為向左移位，兩者皆是將超過範圍的 bits 移除，並將空缺的 bits 補上 0 * 算數移位：sar 以及 sal * 用法: `sar src, dest ` 將 dest 向右移位 src 個 bits，並依照原本的 sign bit 是多少，把空缺位都補上一樣的 0 或 1 * 範例： ``` movw $ff00,%ax # ax=1111.1111.0000.0000 (0xff00, unsigned 65280, signed -256) salw $2,%ax # ax=1111.1100.0000.0000 (0xfc00, unsigned 64512, signed -1024) # (arithmetic shifting left by 2 is like multiplication by 4 for # negative numbers, but has an impact on positives with most # significant bit set (i.e. set bits shifted out)) sarw $5,%ax # ax=1111.1111.1110.0000 (0xffe0, unsigned 65504, signed -32) # (arithmetic shifting right by 5 is like integer division by 32 # for negative numbers) ``` * Aarch32/Aarch64： * 邏輯移位： * 向右移位：LSR * 向左移位：LSL * 算術移位： * 向右移位：ASR * 向左移位：ASL ## 參考 * [邏輯左移、邏輯右移、算術左移、算術右移、循環左移、循環右移](http://blog.csdn.net/u011070169/article/details/53894154) * [X86 Assembly/Shift and Rotate](https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate) * [ARM-Assembly: Arithmetic Shift / Logical Shift](https://stackoverflow.com/questions/14565444/arm-assembly-arithmetic-shift-logical-shift) # 因為自動飲料機而延畢的那一年 - [讀後心得及啟發](https://hackmd.io/YXnTlwD1Ty2rHv4WcZDHzw)
Last changed by  
 
雷承勳
447
Published on HackMD