# 2018q1 Homework2 (assessment)
contributed by < `f74034067` >

### [第 1 週測驗題](https://hackmd.io/s/rJh9U4Guf) 測驗 5
考慮以下整數乘法的實作程式碼:

int mul(int n, int m)
{ 
    int ret = 0;
    for (int c = 0; m; c++, m /= 2)
        if (!(m % 2 - 1)) OP
    return ret;
}

上述 `OP` 對應到下方哪個程式敘述呢？
`(a)` ret = n << c;
`(b)` ret += n;
`(c)` ret <<= n;
`(d)` ret = c << n;
`(e)` ret += n << c;
#### 答案
`(e)` ret += n << c;
#### 想法
首先看到 `if (!(m % 2 - 1))` 中如果 m 為奇數，也就是二進位表示最後一位為 1 時，則會進行 `OP`，再看到 `for` 迴圈會不斷將 m / 2 ，也就是右移，而 c 會不斷累加，用以紀錄 m 右移了幾次，最後可以發現

若 m 的第一個 bit 為 1 ，則 ret += n * 1
若 m 的第二個 bit 為 1 ，則 ret += n * 2
若 m 的第三個 bit 為 1 ，則 ret += n * 4
...

例如若 m = 11，則 ret = n * (1 + 2 + 8)

#### 延伸
若是 m 為負數時，`m % 2`會得出 0 與 -1 兩種可能，所以 `(!(m % 2 - 1))` 只會得出 false 的結果，因此 m < 0 時只會 return 0，乘法無法順利運作。
:::danger
如何修正？不要只有「因為...所以...」這樣的描述，要有推論和改進方案！我們做的是工程訓練，不是考公職。
:notes: jserv
:::

### [第 2 週測驗題](https://hackmd.io/s/SJO5LN9_M) 測驗 3

考慮到某些實數的二進位表示形式如同 $0.yyyyy...$ 這樣的無限循環小數，其中 $y$ 是個 $k$ 位的二進位序列，例如 $\frac{1}{3}$ 的二進位表示為 $0.01010101...$ (y = `01`)，而 $\frac{1}{5}$ 的二進位表示為 $0.001100110011...$ (y = `0011`)，考慮到以下 y 值，求出對應的十進位分數值。

* y = `010011` => $\frac{19}{X1}$
* y = `101` => $\frac{5}{X2}$
* y = `0110` => $\frac{2}{X3}$

#### 想法
利用無窮等比級數的公式，當公比 -1 < r < 1，則總和為 $\frac{首項}{1-r}$
#### 答案
* y = `010011` => 首項 = $\frac{19}{64}$ ，r = $\frac{1}{64}$ => x1 = 63
* y = `101` => 首項 = $\frac{5}{8}$ ，r = $\frac{1}{8}$ => x2 = 7
* y = `0110` => 首項 = $\frac{6}{16}$ ，r = $\frac{1}{16}$ => x3 = 5

### [第 3 週測驗題](https://hackmd.io/s/SknkEfVFf) 測驗 2

:::danger
3 月 26 日的截止時間剩下幾小時了，但我看不到你的充分付出。
:notes: jserv
:::
考慮到下方函式 `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_right_arith : 把最左位元的值填入新的最左位元
1101 0111 => 1110 1011

shift_right_logical : 移走的位填充為 0
1101 0111 => 0110 1011

* 算術右移
* 由 `sizeof(int) * 8` 得知整數型態 `int` 的位元數 `w` 可推得 p1 = 3。
* (int) -1 = $(111...1)_2$ ， mask 只要最左邊的 k 個位元為 1，因此左移 (w - k)
* 由 `if (x < 0)` 可以推算當 x 最左邊的 bit 為 1 時 xsrl 必須把最左邊的 k 個 bits 改回 1 => `xsrl | mask`

* 邏輯右移
* p4 = 3
* (int) -1 = $(111...1)_2$ ， mask 只要最左邊的 k 個位元為 1，因此左移 (w - k)
* 將最左邊 k 個位元填充為 0 => `xsra & ~mask`

#### 答案

#include <stdio.h>
int shift_right_arith(int x, int k) {
    int xsrl = (unsigned) x >> k;
    int w = sizeof(int) << 3;
    int mask = (int) -1 << (w-k);
    if (x < 0)
        return xsrl | mask;
    return xsrl;
}

unsigned shift_right_logical(unsigned x, int k) {
    unsigned xsra = (int) x >> k;
    int w = sizeof(int) << 3;
    int mask = (int) -1 << (w-k);
    return xsra & ~mask;
}

#### 延伸
:::info
延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
:::
* Reference :
* [X86 Assembly/Shift and Rotate](https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate)
* [Arithmetic Shift Operations](http://www-mdp.eng.cam.ac.uk/web/library/enginfo/mdp_micro/lecture4/lecture4-3-3.html)

* x86_64
* **sar** dest, src
Arithmetic shift `dest` to the right by `src` bits. Spaces are filled with sign bit (to maintain sign of original value), which is the original highest bit.

* **shr** dest, src
Logical shift `dest` to the right by `src` bits.

* Aarch32/Aarch64
* r0, r1, **ASR** r2

shift value in `r1` `r2` places right and fill in vacant bits with copies of original most significant bit

* r0, r1, **LSR** r2

shift the binary value of `r1` `r2` places to the right