# 2018q3 Homework5 (bits)
contributed by < [`letticee`](https://github.com/letticee) >

## 環境設定
* 問題

    $ sudo apt install libc6-dev:i386 gcc:i386
    正在讀取套件清單... 完成
    正在重建相依關係          
    正在讀取狀態資料... 完成
    有些套件無法安裝。這可能意謂著您的要求難以解決，或是若您使用的是
    unstable 發行版，可能有些必要的套件尚未建立，或是被移出 Incoming 了。
    以下的資訊或許有助於解決當前的情況：

    下列的套件有未滿足的相依關係：
     gcc:i386 : 相依關係: cpp:i386 (>= 4:7.3.0-3ubuntu2.1) 但它卻將不會被安裝
                相依關係: gcc-7:i386 (>= 7.3.0-27~) 但它卻將不會被安裝
    E: 無法修正問題，您保留 (hold) 了損毀的套件。

* 解決方式
* 依指示安裝有相依的套件後，make 時會產生 error

    $ make
    gcc -O0 -g -Wall -Werror -m32 -lm -o btest bits.c btest.c decl.c tests.c
    /usr/lib/gcc/i686-linux-gnu/7/../../../../i686-linux-gnu/bin/ld: /usr/lib/gcc/i686-linux-gnu/7/liblto_plugin.so: 載入外掛程式時發生錯誤: /usr/lib/gcc/i686-linux-gnu/7/liblto_plugin.so: 錯誤 ELF 類別：ELFCLASS32
    collect2: error: ld returned 1 exit status
    Makefile:13: recipe for target 'btest' failed
    make: * [btest] Error 1

* 安裝 gcc-multilib 可以解決

    $ sudo apt install gcc-multilib

## bits.c
### absVal
* 想法
* ~~考試題目有出現~~
* `x` 為正的話， `x ^ y` 等於 `x`，`~y + 1` ； `x` 為負的話， `x ^ y` 等於 `~x` ，`~y + 1` 為 1，`(x ^ y) + (~y + 1)` 就是 `x` 的二補數

    int absVal(int x)
    {
        int y = x >> 31;
        return (x ^ y) + (~y + 1);
    }

* commit 時會產生 error

    $ git commit
    [bits.c:114]: (error) Shifting signed 32-bit value by 31 bits is undefined behaviour

:::warning
為什麼是 undefined behaviour
:::
* 將 `x >> 31` 改成 `x >> 30 >> 1` 就不會產生 error

    int absVal(int x)
    {
        int y = x >> 30 >> 1;
        return (x ^ y) + (~y + 1);
    }

### addOK
* 想法
* 發生 overflow 的情況
* 正數相加結果為負數
* 負數相加結果為正數
* 判斷 `x + y` 的 sign bit 是否和 `x`、`y` 的相同，若都不同，則為發生 overflow
* `x + y` 的 sign bit 是否和 `x` 的相同 (不同會是 1)：
* `x ^ sum >> 31`
* `x + y` 的 sign bit 是否和 `y` 的相同 (不同會是 1)：
* `y ^ sum >> 31`
* 若上面兩個結果都是 1，則發生 overflow

    int addOK(int x, int y)
    {
        int sum = x + y;
        return !(((x ^ sum) & (y ^ sum)) >> 30 >> 1);
    }

### allEvenBits
* 想法
*