# 2020q3 Homework3 (quiz3)
contributed by < `joe-U16` >
###### tags: `sysprog2020`

### 測驗`1`

針對有號整數的跨平台 ASR 實作如下:

int asr_i(signed int m, unsigned int n)
{
    const int logical = (((int) -1) OP1) > 0; 
    unsigned int fixu = -(logical & (OP2));
    int fix = *(int *) &fixu;
    return (m >> n) | (fix ^ (fix >> n));
}
// OP1 = >>1
// OP2 = m<0

> [Unspecified behavior](https://en.wikipedia.org/wiki/Unspecified_behavior): 程式行為仰賴編譯器實作和平台特性而定

在不同平台對負數執行算數右移時，其`MSB`可能補`0`或`1`，即為一種 Unspecified behavior。

**程式運作原理：**
* `const int logical = (((int) -1) >> 1) > 0;`
* `-1 >> 1` 後，若`MSB`補1，可得到一負整數，在判斷是否大於0後，`logical` 可得 `0`
* `-1 >> 1` 後，若`MSB`補0，可得到一正整數，在判斷是否大於0後，`logical` 可得 `1`
* `unsigned int fixu = -(logical & (m<0));`
* `logical = 0` 時， `m` 不管為正或負， `fixu = 0`，
* `logical = 1` 時
* 若 `m < 0` 則 `fixu = -1`
* 若 `m >= 0` 則 `fixu = 0`
* `int fix = *(int *) &fixu;`
* 可將 `fixu` 從 `unsigned int` 強制轉型成 `signed int`
* `return (m >> n) | (fix ^ (fix >> n));`
* 若 `fix = 0` 則為 return `m >> n`
* 若 `fix = -1` 則 `fix ^ fix >> n` 為 ${\underbrace{11}_\text{n}000000000000}$
* 再跟右移的 `MSB` 為 `0` 的 `m >> n` 做 `|` 後，可使不同平台在做算術右移時，使得得到的結果都向，右移的 `MSB` 為 1 ，不管在哪個平台的行為都一致。

### 測驗`2`

我們可用 `__builtin_ctz` 來實作 [LeetCode 342](https://leetcode.com/problems/power-of-four/). Power of Four，假設 `int` 為 32 位元寬度。實作程式碼如下:

bool isPowerOfFour(int num)
{
    return num > 0 && (num & (num - 1))==0 &&
           !(__builtin_ctz(num) OPQ);
}
//OPQ = &0x1

**程式運作原理：**
`return num > 0 && (num & (num - 1))==0 &&
!(__builtin_ctz(num) OPQ);`
* `num > 0` ，若不成立，則 return `0`
* `num & (num -1) == 0`，若不成立，則 return `0`，可用來確認 `num` 是否為2的次方數。
* e.g. 假設 `num = 4` ，`(0b0100 & 0b0011) == 0` 成立
* `!(__builtin_ctz(num) & 0x1`
* 可判斷 trailing 0-bits in num 是否為奇數，若是奇數代表 `num` 不為 power of 4

### 測驗`3`

針對 [LeetCode 1342. Number of Steps to Reduce a Number to Zero](https://leetcode.com/problems/number-of-steps-to-reduce-a-number-to-zero/)，我們可運用 gcc 內建函式實作，假設 `int` 寬度為 32 位元，程式碼列表如下:

int numberOfSteps (int num)
{
    return num ? AAA + 31 - BBB : 0;
}
// AAA = __builtin_popcount(num)
// BBB = __builtin_clz(num)

> GCC 提供對應的內建函式:
> __builtin_popcount(x): 計算 x 的二進位表示中，總共有幾個 1
> __builtin_clz(x): 計算 x 的二進位中表示中， leading bits 有幾個0

**程式運作原理：**
`num` 為 `non negative integer`
`return num ? AAA + 31 - BBB : 0;`
* 若 `num = 0` ，則 return `0`
* 觀察數字特性e.g.
* `0b00000000000000000000000000000001` 需做`-1`
* `0b00000000000000000000000000000010` 需做`>>1`、`-1`
* `0b00000000000000000000000000000011` 需做`-1`、`>>1`、`-1`
* 可以發現當 `num` 為奇數時，都需要花費一步來讓 `num` 變成偶數才可以繼續做除法，使用 `__builtin_popcount(num)` 就像是計算變成奇數的次數
* 要扣掉 leading bits 是因為 leading bits 有幾個 `0` ，即可少做幾次除法。

### 測驗`4`
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:

#### Q1

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

#include <stdint.h>
uint64_t gcd64(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (XXX);
    return YYY;
}
// XXX = v
// YYY = u << shift

**程式運作原理：**
* 使用算術右移和 `&` 或`+ -` 來取代 `mod` 運算
* 根據阿基里德演算法 `gcd(u, v) = gcd(v, u%v)`
* 根據上述演算法可知 `while(XXX)` 會持續做到 v 為 `0`，故 `XXX = v`
* `for (shift = 0; !((u | v) & 1); shift++) {
u /= 2, v /= 2;
}`
* for 迴圈會持續做到 `u` 或 `v` 其中一個為奇數為止， `shift` 記錄迴圈做了幾次
* 這邊做的是找出 `u`、`v` 最多有幾個因數 `2` ，可以先抵銷掉，在最後 `return u << shift` 再將她乘回來，以方便後續運算。
* `while (!(u & 1))
u /= 2;`
* 讓 `u` 一直右移直到變成奇數
* `10`-`20` 行在找出 `u`、`v`共同擁有的的奇數因數。
* 這段程式碼不像用歐幾里德演算法，他是找出兩個數字所用有的相同因數，而這些因數相乘就會是最大公因數。

## 測驗 `5`

#include <stddef.h>
size_t improved(uint64_t *bitmap, size_t bitmapsize, uint32_t *out)
{
    size_t pos = 0;
    uint64_t bitset;
    for (size_t k = 0; k < bitmapsize; ++k) {
        bitset = bitmap[k];
        while (bitset != 0) {
            uint64_t t = KKK;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}
// KKK = bitset & -bitset

**在原本的程式裡:**
`bitmap` 是一個陣列，裡面存 `64` 位元的正整數
`bitset` 在做一個一個存取 `bitmap` 裡面的正整數
* `for (int i = 0; i < 64; i++) {
if ((bitset >> i) & 0x1)
out[pos++] = p + i;
}`
* `for` 迴圈會跟每個 bit 比較看有沒有 `1`
* 有的話 pos 會加一
* out 會紀錄這個 bit 的位子。

**改良後的程式：**
* 讓 t 是 mask
* `bitset & -bitset` 等價於 `bitset & (~bitset + 1)`
* 其實 t 就會是 `0x0000000000000001`
* 然後 r 是一次可以前進的值，可以讓 out 一次走 r 步，記錄值為 1 的 bit
* 最後 `bitset ^= t` 是把紀錄過的 `1` 變為 `0` 才可以讓 `__builtin_ctzll` 正常運作