2018q1 Homework2 (assessment)
=============================

contributed by <`BodomMoon`>

### 測驗 `W1Q4`

考慮某些硬體平台執行乘法的時間較長，我們會以 `(x << 5) - (x)` 取代 `*` 31，那麼 `*` (-6) 該如何用 shift 搭配 add/sub 實作呢？
`(a)` 2 個 shift 搭配 0 個 add/sub
`(b)` 2 個 shift 搭配 2 個 add/sub
`(c)` 2 個 shift 搭配 1 個 add/sub
`(d)` 1 個 shift 搭配 1 個 add/sub
`(e)` 0 個 shift 搭配 2 個 add/sub

延伸問題:

- 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？

---

### 想法 & 思考
其實應該要知道的是，在任何進位中的表示方式本質上就是 shift 搭配 add ，在二進位中我們可以看成 1 這個單位用 shift 搭配 add 表達出來的數量 (假設下列算式皆為先位移後加減)
`1 * 1011 = 1<<3 + 1<<1 + 1<<0 = 1 * 11`
而這時只要將我們計算的單位從 1 換成 x 但進制保持二進制就是我們題目的目標了。

x * 011111 
= x << 4 + x << 3 + x << 2 + x << 1 + x << 0 
= x * (100000 - 000001)
= x << 5 - x << 0
= x * 31

有沒有看出規律惹～
- 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？

的確有，只要比較乘數轉為二進位的情況下 1 的數量以及乘數無條件進位後與原數差距值 1 的數量即可找出組合最小值得~~唯一~~解。

:::info
延伸問題：似乎可以結合bitmask寫成程式的形式，待後續實作補充
:::

2018/03/27補充
> 剛剛看了`AliennCheng`同學的共筆之後發現我根本沒搞懂題目的意思，連國文系的都不如QQ

同學對這題的解釋更為精闢

是否存在最小值 k 使得表示式 2a1 ± 2a2 ± … ± 2ak 足以表示所有整數，a1, a2, … , ak 為任意相異整數 
by AliennCheng

我的解答並沒有把問題定義清楚，不過某種程度上跟`AliennCheng`同學指出了一個相同的結論，如何公式化的用數學表達

比較乘數轉為二進位的情況下 1 的數量以及乘數無條件進位後與原數差距值 1 的數量並回傳比較小的那個數量

若能在數學上證明此事則本假設有解，但這個假設是可以程式化的，且最簡單的就是用迴圈+if解，有品味的甚至可以嘗試用bitwise運算來達到，至於詳細實作方式還須進一步研究。

> 參照[phonebook開發紀錄](https://hackmd.io/s/B1YMR4YuG#)中間有實驗發現gcc會自動將 a*31 編譯為以 (a<<5)-a 實作的組合語言，可作為佐證 gcc 內部的確已把這個假設程式化。

---

### 測驗 `W2Q3`

考慮到某些實數的二進位表示形式如同 $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}$

---

### 想法 & 思考

~~我找這題寫絕對不是為了偷懶~~
這題簡直簡單到飛起來，在離散數學中提到過：

`0.01111111...INF會無窮接近0.1`

所以光是看第一個為1的數字就可以大概知道該分數的大略位置了，因為後方的數字不管再多都不可能超過這個範圍
* y = `010011` => $\frac{19}{X1}$

故可知 0.5 > y > 0.25 再以0.25為單位可見後續的數從$\frac{1}{8}$開始增加但絕不會超過$\frac{1}{4}$，故可知值的範圍在0.25*1.25 > y > 0.25。接著回頭看一下選項
X1 = ?

- `(a)` 11
- `(b)` 23
- `(c)` 63
- `(d)` 97
- `(e)` 57
- `(f)` 31
- `(g)` 5
- `(h)` 13

僅 `(c)` 63 帶入後 0.25*1.25 > $\frac{19}{63}$ > 0.25
故可證答案為選`(c)`

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

後續兩題都一樣的方法就可得證就不再贅敘。

---
### 測驗 `W3Q2`

考慮到下方函式 `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;
}

### 想法 & 思考

老實說在課堂上第一次看到這段程式碼的時候，我就有一種「這到底在寫三小的感覺」。不是看不懂而是整個function的本質上就是在脫褲子放屁，根本可以改寫成下面這樣

#include <stdio.h>
int shift_right_arith(int x, int k) {
    return x >> k;
}

unsigned shift_right_logical(unsigned x, int k) {
    return  x >> k;
}

其他東西根本都是多的，不過遇到了題目我們還是得認真來解一下。
由於我們在一開始做了轉型強迫右移時補0
`int xsrl = (unsigned) x >> k`
所以我們必須要計算並且判斷一下1是否這個數右移時其實是要補1的，要補的地方在最左邊第64位到k位的位置

int w = sizeof(int) << P1;
int mask = (int) -1 << (P2);

w 為 int 的 bit 數，題目有告訴我們是 *8 了， *8 相等於 >>3 已經是二進位數字系統的常識了
**P1 = 3**
P2 代表的是最左邊第64位到k位的位置
**P2 = w-k**
最後在 P3 的部份我們是要 set 沒改成1的補為 1
所以用 or 或 + 都可以

:::info
額外想法：其實考試時答案只有一個我還挺困惑的，理論上 + 應該也可以阿？按照這個程式邏輯跑下來又不會有溢位問題，得到的答案應該是一樣的，這題是不是答案有錯誤？
:::

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就很直覺得同上 *8 = >>3
P5也是很直覺得同上 w-k
最後的 P6 P7 的目標在於將 64 到 k 位設為 0
故是將 ~mask 去做 & 強制將指定的位數清零並且保持後面的位數不變。

:::info
TODO 延伸題目: 在 x86_64 和 Aarch32/Aarch64 找到對應的指令，並說明其作用和限制
:::

# 閱讀 [因為自動飲料機而延畢的那一年](http://opass.logdown.com/posts/1273243-the-story-of-auto-beverage-machine-1) 的啟發

寒假就看完了，我覺得要相信自己的心，誠實面對自己之後覺得有價值的事情就去嘗試吧，就像我現在每個禮拜跑過來成大一樣，就是因為我相信這是有價值有意義的，每個挫折都是一份收穫，~~期許自己能保持這個暴肝生程式的姿態到畢業~~。

# 學習筆記
:::info
TODO: 基礎太差好難過，程式碼生不完沒空看啦QAQ
:::