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)
Sign in with Wallet
Connect another wallet