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

## 測驗題作答
### 第 1 周第 4 題
考慮某些硬體平台執行乘法的時間較長，我們會以 `(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

:::success
延伸問題:
* 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？
:::
**想法 & 思考**
* 參考 CS：APP 第 71 頁
* 以 $x * 14$ 為例；因為 $14=2^3+2^2+2^1$，所以可以將 $x * 14$ 改寫成 $（x<<3)+(x<<2)+(x<<1)$。又因 $14=2^4-2^1$，所以也可以寫成 $(x<<4)-(x<<1)$。
* 題目欲求的 $*（-6）$ 可以改寫成 $-2^2-2^1$ 或 $-2^3+2^1$，但取後者可以少做一次減法。得 $x *（-6）=(x<<1)-(x<<3)$ ，所以答案為 `(c) 2 個 shift 搭配 1 個 add/sub`
* CS:APP 中有歸納出： $x*K$ 中的 K 如果可以表示成 [(000...0)(111...1)(000...0)] 的形式，且 (111...1) 部份至少有3個1，最高位為第 n 位，最低位為第 m 位（由 0 開始）。則可表示成下列兩種形式
* (x<<n)+(x<<(n-1))+...+(x<<m)
* (x<<(n+1))-(x<<m)
* 由於上述第 1 種表示法有多少 1 就要寫成多少項相加，第 2 種不論 1 的數量有多少都只有兩項。顯然 K 可表示成 [(000...0)(111...1)(000...0)] 形式時，因為 1 的數量必$>=3$，相較而言第 2 種方式可以用較少運算次數達成目標。
* 因此當 K 可表示成 [(000...0)(111...1)(000...0)] 形式時，有最小唯一解

### 第 2 周第 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}$

X1 = ?
* `(a)` 11
* `(b)` 23
* `(c)` 63
* `(d)` 97
* `(e)` 57
* `(f)` 31
* `(g)` 5
* `(h)` 13

X2 = ?
* `(a)` 17
* `(b)` 19
* `(c)` 13
* `(d)` 11
* `(e)` 3
* `(f)` 7
* `(g)` 23
* `(h)` 97

X3 = ?
* `(a)` 23
* `(b)` 19
* `(c)` 17
* `(d)` 13
* `(e)` 11
* `(f)` 7
* `(g)` 5
* `(h)` 3

Reference:
* [Binary Fractions](https://www.electronics-tutorials.ws/binary/binary-fractions.html)
[83]

**想法 & 思考**
* 令循環小數的一組循環有 x 位，則 $0.yyyy...$ 可以想成 0.y, 0.y * $2^{-x}$, 0.y * $2^{-2x}$,.....無窮等比數列之和。其中首項為 0.y ，公比為 $2^{-x}$。
* 無窮等比和的公式為 $\frac{首項}{1-公比}$，帶入後答案為 $\frac{0.y}{1-2^{-x}}$。
* 第一小題 y = 010011，$0.y$ 為 $\frac{19}{64}$，x 為 6 ，帶入公式得 $\frac{19}{63}$ 。因此答案選`(c)63`。
* 第二小題 y = 101，$0.y$ 為 $\frac{5}{8}$，x 為 3 ，帶入公式得 $\frac{5}{7}$ 。因此答案選`(f)7`。
* 第三小題 y = 0110，$0.y$ 為 $\frac{3}{8}$，x 為 4 ，帶入公式得 $\frac{2}{5}$ 。因此答案選`(g)5`。

:::warning
接著你可以繼續思考：「如何一般化 (generalize) 呢？」
給定的分數 (即 N/M 形式，當 N 和 M 都是正整數)，如何轉換成二進位，而且在表達 bit 數量限制的狀況，轉換的誤差是多少？(對比看 CS:APP 提及的愛國者導彈的誤差議題)
:notes: jserv
:::

### 第3周第2題
考慮到下方函式 `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;
}

==作答區==

P1 = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` -1
* `(e)` -2
* `(f)` -3
* `(g)` 0

P2 = ?
* `(a)` 1
* `(b)` k
* `(c)` k - w
* `(d)` w + k
* `(e)` w
* `(f)` w - k

P3 = ? (為某種 operation)
* `(a)` ^
* `(b)` &
* `(c)` <<
* `(d)` |
* `(e)` >>
* `(f)` +
* `(g)` -

P4 = ?
* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` -1
* `(e)` -2
* `(f)` -3
* `(g)` 0

P5 = ?
* `(a)` 1
* `(b)` k
* `(c)` k - w
* `(d)` w + k
* `(e)` w
* `(f)` w - k

P6 = ? (為某種 operation)
* `(a)` ^
* `(b)` &
* `(c)` <<
* `(d)` |
* `(e)` >>
* `(f)` +
* `(g)` -

P7 = ?
* `(a)` mask
* `(b)` ~mask

Reference:
* [Arithmetic Shift Operations](http://www-mdp.eng.cam.ac.uk/web/library/enginfo/mdp_micro/lecture4/lecture4-3-3.html)
(63)

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

**想法 & 思考**
* 先探討算術右移 (shift_right_arith) 的部份
* 從程式碼可知，如果 x>=0 會直接回傳 xsrl，代表 w, mask 只**可能**與 x<0 時有關
* 程式碼第 1 行就先把原本傳入的 x 型態由 int 改成 unsigned ，真是太奇怪了
>[color=green]
>* 參照 CS:APP 第 40 頁可得知，C 語言的移位運算可分為 **算術**及**邏輯** 。算術右移會補上和最高位一樣的數字(1 or 0)，邏輯右移則是直接補 0。
>* 又從 [這個網站](http://ersbroemu.blogspot.tw/2015/09/logical-shiftarithmetic-shift.html) 得知，會由要進行移位的 x 的資料型態決定採用運算或邏輯。如果為 signed 則進行運算位移， unsigned 進行邏輯位移。
* 結論：因為原本該執行算術位移的 x 被改成邏輯位移，不管是否 <0 左邊都會直接補零。因此在 x<0 時，必須把最高位以左的數字全部改成 1。
* 先求總共有 w bits : sizeof(int) 可求出有多少 bytes ， 1 bytes = 8 bits，所以共 (sizeof(int)<<3) bits
* 再求要把哪些位置的 0 改成 1：
* -1 的 2 進位表示法為 $(111...1)_2$
* x 做邏輯右移 k 位後，最左 k bits 為 0
* 將 $(111...)_2$ 往右移 (w-k) 位
* 在選項中選出可使 **1？0=1** 之運算子
* 運算子為 +
* 再探討邏輯右移 (shift_right_logical) 的部份
* 第 1 行將 x 轉換成 (int) 型態，所以會進行算術右移
* 因此當最左邊的數為 1 時，右移後會造成最高位以左都是 1 的情形
* -1 的 2 進位表示法為 $(111...1)_2$
* 最左邊 k bits 需修正，因此將 $(111...1)_2$ 左移 (w-k) 位，形成 $(111...1)(000...0)_2 = mask
* 需留下 xsra 中對應到 mask 數字為 0 的部份，捨去 1 的部份
* 因此取 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;
}

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

去年這篇文剛寫完就因為有學長轉貼而看完了，但那時的我還沒有接觸硬體的經驗，因此就只是覺得，喔 好厲害喔。

但在三上接觸到令成大資工系的學生最崩潰的微算機課程後再讀一次，真的是讓人雙膝一軟。還記得微算機期末專題時，有一個部份是想要利用馬達驅動齒輪組，最後連接到的齒輪可以用秒針的速度運轉。原本大家都覺得這個有什麼好難的，不過就是算每個齒，查一下馬達轉多快，再代入高中學過的公式就可以做出來嗎（？）但開始之後才發現我們太天真了。

由於我們是窮學生經費有限，買的馬達電壓不穩，轉速會忽快忽慢；再加上齒輪組沒有精細到像我們想像的完全咬合，因此算了整個下午做出來的成果......(◢▆▅▄▃ 崩╰(〒皿〒)╯潰 ▃▄▅▆◣)最後是直接~~隨便~~拿一堆齒輪去接馬達，勉強**湊**出一組還算滿意的結果。

看完這篇文章後除了覺得他突破硬體障礙很厲害外，也對他不放棄的精神感到非常佩服。想想有多少人願意為了一個不一定做得出來的東西而延畢?就算願意，敢實際去這麼做的人又有多少?要想想延畢背後的成本有多少，包括以後工作面試可能被刁難、家人不諒解、時間金錢成本等等。但他仍願意承擔來達成夢想，這種勇於達成自己夢想的精神值得我們學習。

## 三周課程啟發
* 雖然之前就有聽說過這堂課蠻操的，有做好心理準備，但真的開始修還是常被震撼到。像是有將近一半的學生是來自外系但感覺都好強，每周都有超級多的影片要看，還沒有哪次小考最高分是資訊系大三(QQ)，還有每次看到高手的開發紀錄都自嘆弗如。有時候還是會蠻挫折的，覺得自己是不是怎麼努力還是會比不上那些大神們；而且因為要撥時間讀之後要考研究所的書，儘管已經花比以往都還要多的時間坐在書桌前，還是覺得時間不夠用。但還是希望自己能繼續撐下去，好好修完這堂課，成為一個~~就算撕掉畢業證書還是~~找的到好工作的人。

## 課後學習
* 聽 [現代處理器設計：原理和關鍵特徵](http://hackfoldr.org/cpu) 才發現自己連 ARM MIPS x86 等名詞都只是聽過而不知道那是什麼，覺得很荒謬，所以找了些東西來看。
* [ARM 處理器的發展](https://hellolynn.hpd.io/2017/04/14/%E7%9C%8Barm%E5%A6%82%E4%BD%95%E6%90%B6%E8%B5%B0x86%E5%B8%82%E5%A0%B4%EF%BC%9F%E8%8B%B1%E7%89%B9%E7%88%BE%E8%A2%AB%E9%80%86%E8%A5%B2%E4%B8%8B%E7%9A%84%E7%AD%96%E7%95%A5/)
* CS：APP 第四章
* [現代處理器設計: Cache 原理和實際影響](http://hackfoldr.org/cpu)
* SIMD miss 造成極大代價
* MMX 及 SSE 為 SIMD 擴充指令集
* unpack
* [0xff07 HackMD 筆記](https://hackmd.io/s/H1d_W-gsg)

###### tags: `bauuuu1021`, `sysprog`