# 2018q3 Homework5 (bits)
contributed by < `happyincent` >

## Environment

$ cat <(echo "CPU:    " `lscpu | grep "Model name" | cut -d':' -f2 | sed "s/  //"`) <(echo "OS:     " `lsb_release -d | cut -f2`) <(echo "Kernel: " `uname -a | cut -d' ' -f1,3,14`) <(echo "gcc:    " `gcc --version | head -n1`)
CPU:     Intel(R) Xeon(R) CPU E5520 @ 2.27GHz
OS:      Ubuntu 16.04.5 LTS
Kernel:  Linux 4.15.0-38-generic x86_64
gcc:     gcc (Ubuntu 5.4.0-6ubuntu1~16.04.10) 5.4.0 20160609

#### Install `gcc-multilib`

$ echo "int main(){}" | gcc -xc -m32 - &>/dev/null; echo $?
1
$ sudo apt install gcc-multilib
...
$ echo "int main(){}" | gcc -xc -m32 - &>/dev/null; echo $?
0

## bit.c

### 1. satAdd
> 確認 x+y 是否 overflow，並在發生 (+/-) overflow 時 retuen 最大 or 最小整數

* 取出 x, y, x+y 的 sign bit，在 `正+正=負` 或 `負+負=正` 時發生 overflow
* 最小整數 = `0x80 << 24`，最大整數: `最小整數 - 1`

int satAdd(int x, int y)
{
    int x1 = (x >> 31) & 0x1;
    int y1 = (y >> 31) & 0x1;
    int test = x + y;
    int t1 = (test >> 31) & 0x1;

    // 0 0 0
    // 0 0 1 V
    // 0 1 0
    // 0 1 1
    // 1 0 0
    // 1 0 1
    // 1 1 0 V
    // 1 1 1

    unsigned min = 0x80 << 24;
    unsigned max = min - 1;

    unsigned o1 = x1 & y1 & !t1;
    unsigned o2 = !x1 & !y1 & t1;
    unsigned check = o1 | o2;

    return ((((~(!o1) + 1) & max) | ((~(!o2) + 1) & min)) & (~(check) + 1)) |
           ((~(!check) + 1) & test);
}

### 2. bang
> 計算 !x

* 位移後做 or 運算，只要有其中一個 bit 為 1，就會得到 1 並 return `~x & 0x1` 得到 0

int bang(int x)
{
    unsigned mask = (0xff << 8) + 0xff;
    x = (x >> 16) | (x & mask);
    x |= x >> 8;
    x |= x >> 4;
    x |= x >> 2;
    x |= x >> 1;
    return ~x & 0x1;
}

### 3. byteSwap
> 對調 x 的第 n, m 個 byte
> Example: byteSwap(0xDEADBEEF, 0, 2) = 0xDEEFBEAD

* 以 mask 取出不變的 byte，e.g.
* n=1, m=3, mask = `00ff00ff`
* 取出第 n byte `0x000000EF` 右移 n byte 至第 0 byte，左移 m byte 到欲交換的第 m byte `0x00ef0000`
* 轉 unsigned 做 zero extension 的右移
> GNU GCC 3.8 - [Bit Shifting](https://www.gnu.org/software/gnu-c-manual/gnu-c-manual.html#Bit-Shifting)
> C99 - 6.5.7 - 5
> The result of E1 >> E2 is E1 right-shifted E2 bit positions.
> If E1 has an **unsigned type** or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2^E2^.
* 對第 m byte 重複上述操作

int byteSwap(int x, int n, int m)
{
    unsigned y = x;
    unsigned mask = ~((0xff << (n << 3)) | (0xff << (m << 3)));
    return ((y & mask) | ((y & (0xff << (n << 3))) >> (n << 3) << (m << 3)) |
            ((y & (0xff << (m << 3))) >> (m << 3) << (n << 3)));
}

### 4. fitsBits
> 判斷 x 是否可以 n-bit two's complement 表示

[[source](https://en.wikipedia.org/wiki/Two%27s_complement)]
* 由上圖可以看出最小 n-bit 的 2's complement 整數
* n=1, 111, 第 0 個 bit 開始為 1
* n=2, 110, 第 1 個 bit 開始為 1
* n=3, 100, 第 2 個 bit 開始為 1
* 因此在最小負數情況下
* `x >> 31` 後為 `0xffffffff`
* 將 x 右移 `n - 1` 個 bit 後為 `0xffffffff`
* XOR 兩者後得到 `0x00000000`
* 在最大正數情況下，結果一樣
* `0x00000000` ^ `0x00000000` = `0x00000000`

int fitsBits(int x, int n)
{
    // 1 : 0 ~ -1
    // 2 : 1 ~ -2
    return !((x >> 31) ^ (x >> (n - 1)));
}

### 5. isAsciiDigit
> 判斷是否屬於 ASCII 的數字 '0' 到 '9'
> (return 1 if 0x30 <= x <= 0x39)

* 條件
* `x - 0x3A` < 0
* `x - 0x30` ≥ 0

int isAsciiDigit(int x)
{
    return ((x + (~(0x3A) + 1)) >> 31) & (~((x + (~(0x30) + 1)) >> 31) & 0x1);
}

### 6. rotateRight
> 向右輪轉 n (`0 <= n <= 31`) 個 bit
> Examples: rotateRight(0x87654321, 4) = 0x18765432
> (題目 Example 有錯)

* 以 mask 取出要 rotate 的 bit，e.g.
* n=4, mask = `00000010 - 1` = `0000000f`
* 左移的部分 `<< (32 - n)`，右移的部分 `>> n`

int rotateRight(int x, int n)
{
    unsigned mask = ((0x1 << n) + ((~1) + 1));
    return ((x & mask) << (32 + (~n +1))) | ((x & (~mask)) >> n);
}

### 7. upperBits
> 將 n 個 upper bits 填上 1

* `!!n & 0x1`
* 0 -> 0x0
* 非 0 -> 0x1
* [wiki](https://en.wikipedia.org/wiki/Two%27s_complement) 的 2's complement 舉例:
> The two's complement of an N-bit number is defined as its complement with respect to 2^N^.
> For instance, for the three-bit number 010, the two's complement is 110, because 010 + 110 = 1000.

* 將 1 左移 `32 - n` bit 再做 2's complement 運算後即可產生前 n 個 bit 為 1 的結果

int upperBits(int n)
{
    int x = ((!!n & 0x1) << (32 + (~n +1)));
    return (~x + 1);
}