2018q3 Homework5
===
contributed by < `chenishi` >

### 作業大綱
增進對於 C 語言數值運算實做上的理解，像是針對整數與浮點數的 bit-wise operation 等等在，這些數學表示觀念在 C99 規格書更是獲得了[巨量的擴充](/s/Hy_oBnIsX#)
因此詳細理解數值系統才能避開許多像是 undefined behavior 導致的資安議題

### 作業目標
github 上 clone [datalab 專案](https://github.com/sysprog21/datalab)到本地端，修改/ 實做 datalab/bits.c 內的函式

  int Funct(arg1, arg2, ...) {
      int var1 = Expr1;
      ...
      int varM = ExprM;

      varJ = ExprJ;
      ...
      varN = ExprN;
      return ExprR;
  }

以上是建議的 coding style
同時 Expr 只限以下組成
* 區域變數（並不會使用到全局變數）
* 整數常數範圍只限定由 0 ~ 255，不允許使用過大的數 (EX: 0xFFFFFFFF)
* 只允許 unary 整數運算符（像是 ! ~）以及 binary 運算符 (像是 & ^ | + << >>)

Expr 中不能存在
* 條件判斷(像是 if else while for do switch 等等)
* 巨集 macro(同時也代表不能自行 \"#include\" 函式庫)
* 外部連結檔案
* 函式呼叫
* 其餘運算符（像是 &&, ||, -, ?:）
* 強制轉型
* int 以外的資料型態（這也代表不能使用 array struct union）

同時有幾點情況需要注意
* 位元位移量超過 0~31 的行為是 implementation behavior，根據編譯裝置架構不一可能有不同的實做；在這邊可以視為裝置不確定所以表現也不固定

### Q: absVal(int x)
*以 int 形式回傳 x 絕對值*

int absVal(int x)
{
    /* 取得 sign bit
       sign bit 也可以用 mask（x | 0x8000）
       不過題目有限定不能用超過 255 的 int */
    int sign = x >> 31;
    /* 如果是正數，括號內就會是原本數值，後項也會因為 sign bit 為零而消去
       複數的話括號內會變成 ~x，sign bit 等於一正好符合2補數操作*/
    return (x ^ sign) - sign;
}

:::info
要注意到像是 `(x | 0)` `(x ^ 0)`這類的操作在 binary 中效力等同於 `~x`
:::

### Q: isNonZero(int x)
*只要輸入不是零的話，全部都回傳 1，反之回傳 0*

:::info
這題看似簡單，最直覺的方法是「用一個 for loop 遞迴 or 每一個 bit（過程中只要有一個 1 結果就會是一）」，不過很可惜的是，不准用遞迴
:::

下列方法都是出自於[ stackoverflow 上相關的解法](https://stackoverflow.com/questions/3912112/check-if-a-number-is-non-zero-using-bitwise-operators-in-c)

#### * 方法一

int isNotZero(unsigned int n){
  n |= n >> 16;
  n |= n >> 8;
  n |= n >> 4;
  n |= n >> 2;
  n |= n >> 1;
  return n & 1;
};

雖然這個解法並不符合題目敘述（operation 數目必須小於 10）
不過這個方法用到的思考模式非常重要，改變順序或運算符就可以達到其他效果

> 以 isNotZero(0x10100101)為例
> 
> line 2 中 `n |= n >> 16;` 目的就在於**壓縮一半資訊**
> 將前半部份位元壓縮到後半位元內，因此此操作後前半位元就失去了實際意義

>
> 重複以上步驟，可以看到實際有意義的位元數一直減半
> 最後可以把原本長達 32 bits 的資料簡化到剩 1 bit 有效

#### * 方法二

int isNotZero(unsigned int n){
   return ((n | (~n + 1)) >> 31) & 1;
}

以上這個方法就是特殊解了，觀念很難應用在其他問題上
這個方法需要用到 2s' complement 一個很重要的性質（也是它跟 1's complement 主要差別所在）
那就是 **2s' complement 中，+0 與 -0 有同樣的表示法**
相較於零以外其他數字變號時，至少 sign bit 都會有所變化
因此 1 | 0 必然為 1，不過在零的情況，因為正負零表現相同，故 0 | 0 為 0

### Q: conditional(int x, int y, int z)
*用法等同於 return (x) ? y : z*
:::info
這題的思路講破了很直覺，把 x 轉換成 bool 然後產生出對應的 mask
在 true 時讓 y 通過，false 時讓 z 通過

不過說起來簡單，還是需要腦洞大開才會想的到
:::

int conditional(int x, int y, int z)
{
    /* int2bool on x */
    int bool_cond = !!x;
    /* copy single bit to whole word */
    int mask = (bool_cond << 31) >> 31;
    return (x & mask) | (z & ~mask);
}

Line 2 是一個相當有用的技法，非常快速的就可以把 int 轉成 bool

Line 4 產生一個遮罩，如果剛剛 bool_cond 得到 1 的話，就可以把它擴充成 0xFFFFFFFF ，反之則為 0x0

有了這個遮罩，我們就可以選擇性的讓 y 或 z 通過了

### Q: fitsBits(int x, int n)
*如果 x 存在於 n bit 表示範圍內，則回傳 1 反之回傳 0*

int fitsBits(int x, int n)
{
    int remain_high_bit_num = 33 + ~n;
    return !((x << remain_high_bit_num) >> remain_high_bit_num) ^ x;
}

這一題的寫法也是需要[腦洞大開](https://stackoverflow.com/questions/14792521/bitwise-operations-and-shifts)
首先是 Line 1 的 `33 + ~n` 其實應該是 `32 + (~n + 1)` 化簡
其目的就在拿到「n bits 所不能表示的 bit 數目」
Line 2 可以拆成兩部份來看， `(x << ...num) >> ...num` 之後只有使用到這些「n bits 所不能表示的 bit」者才會被 sign extention 掉，進而導致結果與原本 `x` 產生差異
而外層包的 `!(x ^ y)` 結構其實等價於 `x == y`