# 2019q3 Homework3 (quiz3)
contributed by < `uccuser159` >

:::danger
注意細節！第一行有明確的格式規範
:notes: jserv
:::

## 測驗 1

考慮深度學習領域中，使用激勵函數 ReLU：
$$
ReLU(x) =
\begin{cases}
x & \text{if } x \geq 0 \newline
0 & \text{if } x \lt 0
\end{cases}
$$
RelU 計算量小，只要判斷輸入是否大於 `0`，沒有指數運算。下方程式 (`ReLU.c`) 是個常數時間的實作:

float ReLU(float x) {
    union {
        float f;
        int32_t i;                          
    } out = {.f = x};
    out.i = out.i OP1 ~(out.i >> V2);
    return out.f;
}

==思考==

* 在 [union](https://www.itread01.com/content/1498650967.html) 中，全部的共用體成員共用一個空間，而且同一時間僅僅能儲存當中一個成員變量的值。
1. union 中能夠定義多個成員，且 union 的大小由最大的成員的大小決定。
2. union 成員共享同一塊大小的儲存空間， 一次僅僅能使用當中的一個成員。
3. <s>對某一個成員賦值</s> 當指定數值到特定的成員時，由於他們共享一塊儲存空間，會覆蓋其它成員的值。

:::danger
避免用彆扭的詞彙書寫，傳統台灣科技刊物不用「賦值」這詞來表示 assignment，而該用簡單明確的話語來陳述。請尊重台灣資訊科技前輩的付出，儘量用傳統術語和書寫方式。
:notes: jserv
:::

:::warning
從第一手資料找出 union 的描述，翻閱 C 語言規格書，摘錄並解析
:notes: jserv
:::

* 分析 ` out.i = out.i OP1 ~(out.i >> V2)` ：
* 由於 ReLU 函式要判斷輸入數值的正負，所以`~(out.i >> V2)`要取參數 x 的 sign bit，可以得到 V2 = 31。
* 若 $x<0$ ，則`~(out.i >> 31)`得到的結果為111...11(32bits)；若 $x>=0$ ，則`~(out.i >> 31)`得到的結果為000...00(32bits)
* 與參數做 AND 運算恰好即是 ReLU 函式的定義： $x<0$ → $ReLU(x)=0$；$x>=0$ → $ReLU(x)=x$，所以 OP1 填入 &。

* 延伸問題

---

## 測驗 2

在 8 位元 Motorola 6809 處理器上，有道指令叫做 SEX，寓意是 "Sign EXtend"

`SEX 123` 應該輸出 `0`, 而 `SEX -3` 要輸出 `0xffffffff` (取決於有效位數)
考慮一個 32 位元版本的 `SEX` 實作如下，假設執行環境是 little-endian:

#include <stdint.h>
static inline uint32_t sex32(int32_t x) {
    union {
        TYPE w;
        struct { uint32_t lo, hi; }; /* FIXME: little-endian */
    } z = {.w = x};
    return z.hi;
}

==思考==

因為要判別正負號，又 union 能保存不同的數據類型，所以`struct{uint32_t lo, hi; }`結構的大小(64 bits)要與`TYPE w`相同，所以`TYPE` 應為 uint64_t，最後回傳參數 x 做 sign extend 的 `w.hi` 部分。

* 延伸問題

1.解釋程式運作原理，並改寫為適用於 big/little-endian 的程式碼

#include <stdint.h>
static inline uint32_t sex32(int32_t x) {
    union {
        TYPE w;
        struct { uint32_t lo, hi; }; /* FIXME: little-endian */
    } z = {.w = x};
    if(z.hi==0 || z.hi==-1)
        return z.hi;
    else if(z.lo==0 || z.lo==-1)
        return z.lo;
    else
        return;
}

:::warning
避免執行時期的條件判斷，透過 C preprocessor 改寫為編譯時期處理 endian 議題
:notes: jserv
:::

參考資料：[Big/Little Endian](https://blog.gtwang.org/programming/difference-between-big-endian-and-little-endian-implementation-in-c/)

## 測驗 3

延伸測驗 `2` 的 `sex32`，用以改寫 [解讀計算機編碼](https://hackmd.io/@sysprog/rylUqXLsm) 提及的常數時間 `abs` 實作 (輸入是 32 位元整數)，程式碼如下:

static inline int abs_with_sex(int x) {
    return (x ^ sex32(x)) OP2 sex32(x);
}

==思考==

* `sex32(x)` 的作用為判別正負號，可以作為 mask ：
* $x<0$ 則 `sex32(x)`=111...11(32 bits)
* $x>=0$ 則`sex32(x)`=000...00(32 bits)

因為 ==x ^ 1 = ~x== 、 ==x ^ 0 = x== ，所以透過 XOR 的特性，當作`(x ^ sex32(x))`此運算，分為兩種情況：

* $x<0$
要將一個小於 0 的數做 abs() ，即是將此數取2補數。此時的 sex32(x)=111...11(32 bits) ，且與 x 作 XOR 運算得到 ~x ，sex32(x) 的值又為 -1，所以 abs(x) = ~x - (-1)，OP2 為 ==-==

* $x>=0$
要將一個大於 0 的數做 abs() ，即是原來的數。此時的 sex32(x)=000..00(32 bits) ，且與 x 作 XOR 運算得到 x ，sex32(x) 的值又為 0，所以 abs(x) = x - 0，OP2 為 ==-==