2018q3 Homework4 (assessment)
=====
Contributed by <`yichung279`>
###### tags: `sysprog2018`
## 2018q3 第 4 週測驗題 (上)
考慮以下求絕對值的程式碼:

#include <stdint.h>
int64_t abs64(int x) {
    if (x < 0) return -x;
    return x;
}

移除分支並善用[二補數](https://en.wikipedia.org/wiki/Two%27s_complement)特性，改寫為下方程式碼:

#include <stdint.h>
int64_t abs64(int64_t x) {
    int64_t y = x A1 (A2 - 1);
    return (x A3 y) - y;
}

請補完，其中 `A1` 和 `A3` 都是 operator。
A1 = `>>`; A2 = `64`; A3 = `^`;

想法：
1. 因為正負數最大的差異就是最高有效位元(Most significante bit)，其為 signed bit，若 int 正為 1，若 int 負為 0，A1 A2可以馬上假設為 `>>` 及 `64`。
2. 由於 sign extension，我們可以知道 y 為 0b111......1 或 0b000......0。
3. 如果是正數，x 不變。
4. 回想二補數規則，第一步01互換，第二步+1。
5. 如果是負數，我們首先要對x做01互換，而這正是 bitwise 操作中，與 111...1 做 xor ，得到 A3 = ^。
6. 如果是負數，我們第二步要+1，而 +1 就是 -(-1) ，就是 -(0b111111111)。
7. 代回程式驗證。
:::success
延伸問題:
1. 解釋運作原理，並探討可能的 overflow/underflow 議題;
>由於這邊有 -(-1) 的動作，overflow 發生在 x ^ y = 0b0111...1。
>會執行 -(-1)，x^y = 0b0111...1，滿足以下條件的 x 正好有 0b1000...0
>
3. 搭配下方 pseudo-random number generator (PRNG) 和考量到前述 (1)，撰寫 `abs64` 的測試程式，並探討工程議題 (如：能否在有限時間內對 int64_t 數值範圍測試完畢？)

static uint64_t r = 0xdeadbeef
int64_t rand64() {
    r ^= r >> 12;
    r ^= r << 25;
    r ^= r >> 27;
    return (int64_t) (r * 2685821657736338717);
}

3. 在 GitHub 找出類似用法的專案並探討，提示：密碼學相關
:::

## 閱讀心得：因為自動飲料機而延畢的那一年，在學習本課程 4 週之後的感想

這讓我想到我那時候去 makeNTU，要做一個看到陰雨天會自動收起的曬衣架，那時候有一大段時間在弄馬達，「這他媽不是我給他電他就會動嗎?」我大喊，而按下開關後迎來的，卻是一陣尷尬。光是掛一件衣服，小小的馬達就轉不動了，世界還真不是想的那麼簡單。很多時候不要說知道該怎麼解決問題，光知道哪裡有問題就辦不到了。

3D列印的地方也是心有戚戚焉，暑假去香剛交換剛好也是用到玩具等級的3D列印，那時候做一個圓形的護條，明明繪圖軟體上還留有空間，做出來的東西直接斷給我看，於是就畫了好幾次3D繪圖，一種需求好幾種設計，一種設計好幾種畫法，畫一畫差點就轉系了。但我想真正的高手會知道背後有什麼問題，不需要像我試好多次，跟著原則走，畫個幾次就了吧。

還有現在應該要站在巨人的肩膀上，有時候做自己要做的東西的時候應該先查查是不是有人寫好了，像我在做機器學習預處理的時候，常常用到矩陣的操作，一開始超級菜的時候，都自幹 tensor 操作，但明明 numpy 有很多便利的 api，而且numpy 在眾神的加持下，效能遠勝自幹的 tensor，安全性也遠勝自幹。

最後，因為正好小弟本人我，家裡開飲料店（名字有數字有顏色的那家)，消費者買純茶的分析其實不用那麼複雜，像我家單杯平均28塊左右，一杯青茶25塊，一杯波霸奶茶45塊，想觀察消費者怎麼買應該不用這麼黑魔法，問老闆可能更直接。

看到冰塊的時候有不同的想法，這部分有些努力可能白費了，因為除非你掌握茶溫(似乎沒看到這件事)，不然你冰塊量多準確都是白搭，一桶茶剛出來，茶溫高，冰塊加滿雪克杯，他還是去冰給你看，茶放久了一點，八分滿的雪克杯，搖完了冰還是跟你說Hihi。雖然我家的做法不是那樣，但我認為最適合的做法是五十嵐長榮店的做法（對，看店員的時候，我會順便觀察這種東西，），他們的做法是先加過量的冰塊，再把他撈出來，浮力會幫你做事，會幫你把冰塊浮到上層，控制最後剩下的浮冰量就好，不要控制一開始加進去的量，而撈出來這件事又很簡單，跟做實驗時平匙的做法一樣，一根棒棒沿著杯口滑過去，少冰就完成了，去冰就撈深一點，簡單、暴力、繞過去。

看到最後那複雜的電路，突然很慶幸 makeNTU 時我找的隊友很強大，不然我一定吐血，雖然我們電路沒那麼複雜，但我完全能想像debug有多費神。

回到心得，我最大的想法就是，問題的底下永遠有問題，要站在巨人的肩膀上才能避免被問題底下的問題坑殺。就像我當初以為馬達有電（還有波型的問題喔>.^）就要動，就像分配冰塊很困難，但精準分配完冰塊，其實還是其他問題（茶溫）。開發軟體的時候何嘗不是如此，因此我們更要站在巨人的肩膀上。就像我當初專題做，做降水即時預測，但其實香港理工大學已經出了兩篇論文解決相同的問題，　keras　甚至有相關　api　可以用，前一年試著做影像處理，結果搞出一堆垃圾，明明別人就弄完了，何苦呢？

而我期待在這堂課上看到更多像這樣的細節，我期待去細究這些東西。但這也是我一直很掙扎的，我最想去學的更應用面的，網頁技術阿，機器學習阿，跟 C 真的離滿遠的，我甚至不認為我以後還有機會以 C 為主來開發。而跟這衝突的點是，我認為學這些看似離我發展方向，我相信我學會這些東西對我更深入離解一團糟的 JavaScript ，我相信學 C 可以幫助我了解 Python 的運作，如果以後我要需要考慮效能要對 Python　魔改時，修這堂課會有幫助，但這是不確定的。而我基礎其實不好，大三才開始認真寫程式，計組程度很糟（但演算法修得蠻認真的），一直看不到研究所學長的車尾燈蠻累的。但我想變強RRRRR。總之，修這堂課時我一直是很矛盾的，中途甚至放棄作業（還是有在寫自己的東西啦），差點退選，。

拉力： 我想變強，學長推薦（uno、dada)
推力： 很累，程度不足（特別是 OS 跟計組的部分），發展方向沒那麼底層，對 C 不熟（可以說我大四才會指標）

總總之，「頭都洗了，就洗到底吧」我會好好補完功課的 QQ。