# 2018q1 Homework2 (assessment)
contributed by <`BroLeaf`>
###### tags `BroLeaf`
## 第 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;
}
```
上述 `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 週測驗題 第一題
```clike
#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`。
```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;
}
```
* 想法
從兩者的 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