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

## 第 1 週測驗題 第五題
考慮以下整數乘法的實作程式碼:

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;

### 解題思維

先把程式碼做一些分析，看到函式 OP 前面的條件式

 !(m % 2 - 1)

就是這整個程式的關鍵，把他分解來看
`(m % 2)` 如果 m 是奇數，就是 true
`(m % 2 - 1)` 則反過來，如果 m 是偶數，才是 true
`!(m % 2 - 1)` 就簡單了，如果 m 是奇數，就是 true
也就是說 `(m % 2)` 和 `!(m % 2 - 1)` 在邏輯上會是等價的，至於為什麼要多此一舉寫得更複雜呢？可能是老師希望我們多動一些腦？
再來看 for loop 每次的變化 `m /= 2` 看到這裡應該就明白， for loop 每次做的就是看 m 的二進位表示，最右邊一位是不是 1 ，如果是的話就執行 OP
這樣應該可以輕鬆猜出答案是 (e) 了，也就是每次看 m 從右邊數過來第 c 位，如果是 1 的話就讓 ret += $n^c$

### 延伸問題
#### 解釋為何乘法可運作？
如同我上面所述的，每次只看 m 的一個 bit 去對 n 作位移，再把所有結果加總起來，如果用數學式子可以表達成：
令 $m = (c_0*2^0 + c_1*2^1 + c_2*2^2+......+c_n*2^n)$
$\Rightarrow n*m = n*(c_0*2^0 + c_1*2^1 + c_2*2^2+......+c_n*2^n)$
展開後第 n 項就是 for loop 跑第幾次所加上去的值

## 第 2 週測驗題 第一題

#include <math.h>
static inline float u2f(unsigned int x) { return *(float *) &x; }

float exp2_fp(int x) {
    unsigned int exp /* exponent */, frac /* fraction */;

    /* too small */
    if (x < 2 - pow(2, Y0) - 23) {
        exp = 0;
        frac = 0;
    /* denormalize */
    } else if (x < Y1 - pow(2, Y2)) {
        exp = 0;
        frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4));
    /* normalized */
    } else if (x < pow(2, Y5)) {
        exp = pow(2, Y6) - 1 + x;
        frac = 0;
    /* too large */
    } else {
        exp = Y7;
        frac = 0;
    }

    /* pack exp and frac into 32 bits */
    return u2f((unsigned) exp << 23 | frac);
}

### 初步了解
可以搭配 CS:APP 3/e 78、80頁來觀看，以單精度浮點數 32-bit 來看
|情況|signed bit|exponent|mantissa|
|:-:|:-:|:-:|:-:|
|無限大|X|11111111|0000....00|
|NaN|X|11111111|XXXX....XX |
|non-normalized|X|00000000|XXXX....XX|
|最小(負的)|1|00000000|0000....01|
|$\wr$|1|00000000|1111....11|
|-0.0|1|00000000|0000....00|
|+0.0|0|00000000|0000....00|
|$\wr$|0|00000000|0000....01|
|最大(正的)|0|00000000|1111....11|
|normalized|X|XXXXXXXX $\neq$ 0 , 255|XXXX....XX|
|最小(負的)|1|11111110|1111....11|
|最大(正的)|0|11111110|1111....11|
有了上面表格的基本認識，接下來就可以分析程式碼了
* too small
$2^x$ 小到連 float 都不能表示出來，也就是比 float 最小的值還要小 $2^{-126} \times 2^{-23} = 2^{-149}$
接著就可以得到 $2 - pow(2, Y0) - 23 = -149$
移項一下 $pow(2,Y0) = 126$
得到 $Y0 = 7$

* denormalized
這裡是處理 non-normalized 的情況，exponent 的部份都是零，數值界於 $2^{-149}$ ～ $2^{-126}$
經過上一個的 if 條件可以知道 $x > -149$
所以 $Y1 - pow(2, Y2) = -126$
$pow(2, Y2) = 128$
$Y1 = 2，Y2 = 7$

接著來看
`frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4));`
有沒有發現這和 too small 的部份一模一樣，第一次做這題還不會的時候直接讓我矇到答案，答案跟第1題是一樣的，這次來做一個完整的探討
這題要我們用 (unsigned int) frac 去代表 $2$ 的次方
表示後面的值一定要會是正的
exponent 和 mantissa 最多可以代表 $2^{-149}$
而 $x - (-149)$ 代表偏移量，也就是往右移 149 bit 的意思
但我們最後要的只是偏移 148 bit ，所以最後會再左移 1 bit
用 $x = -149$ 帶入檢查，因為要使最後一個 bit 為 1
所以最後的確要左移 1 bit
$Y3 = 7,Y4 = 23$
* normalized
這一段要看的是 normalized 的最大限制
exponent 的值是 $-126 ～ 127$
簡單就能看出 $pow(2, Y5) = 128$
$Y5 = 7$
在這裡要把扣過的偏移值加回來，偏移值可以從 exponent的範圍知道
也可以從 IEEE754 對 單精度浮點數的定義： $2^{k - 1}-1 = 127$
所以 $pow(2, Y6) = 128$
$Y6 = 7$
* too large
根據表格，無限大 exp 部份是 11111111 也就是 0xff
$Y7 = 0 \times ff$

### 延伸問題
#### 給定一個單精度的浮點數值，輸出較大且最接近的 $2^x$ 值，需要充分考慮到邊界
#### 想法
* 如何表達更精確，捨入更精準
* 有效位數?
## 第 3 週測驗題 第二題
考慮到下方函式 `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;
}

* 想法
從兩者的 input 就知道是在處理 signed/unsigned int 的右移問題
算術右移處理 signed 邏輯右移處理 unsigned
* shift_right_arith
首先，根據題目 w 是 int 的 bit 數，所以是 sizeof(int) * 8 ，也就是左移 3
$P1 = 3$
再來是針對負數的操作，要先知道 signed int 的負數是扣掉偏移量的，也就是我們期望的負數右移，在最左邊是要補 1 的，而不是預設的 0
這樣 mask 的作用就很明顯了，就是把右移掉的 1 補回最左邊，要補的位數是最左邊數過來 k 位，所以
$P2 = w - k$
`return xsrl P3 mask;`這段就是在問 0 跟 1 做什麼運算出來會是 1所以簡單得出
$P3 = |$
* shift_right_logical
跟上一題一樣
$P4 = 3$
$P5 = w - k$
而 P6,P7 為了使最左邊共 w - k 位補零，所以為了使 1 轉變成零，應該選擇 and 與 ~mask
$P6 = \&$
$P7 = ~mask$

### 延伸題目
#### 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
* x86_64
* Arithmetic shift
左移是 sal ，右移是 sar
* Logical shift
左移是 shl ，右移是 shr
* 語法
根據[參考連結](https://en.wikibooks.org/wiki/X86_Assembly/Shift_and_Rotate)這部份有點奇妙，所以特地拿出來講，
`GAS syntax` 下語法是 `sal/sar/shl/shr src, dest`
`intel syntax` 下語法是 `sal/sar/shl/shr dest, src`
GAS syntax 也稱為 AT&T syntax ，兩者之間不只 shift 的 src, dest 位置相反，其實還有更多語法用法不同
參考：[Intel and AT&T Syntax.](http://www.imada.sdu.dk/Courses/DM18/Litteratur/IntelnATT.htm)
* Aarch32/Aarch64
* Arithmetic shift
右移是 ASR
* Logical shift
左移是 LSL ，右移是 LSR