# 2020q3 Homework3 (quiz3)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`

---

## 測驗 `1`
下方的程式碼時做出跨平台的算術右移

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

- `logical` 用來判斷該環境下負數右移的結果，若右移補 0 的話則會等於 1

- `fixu` 在以下狀況才會有值 :
- `logical` 為 1 (該環境下右移補 0
- `m` 小於 0

而該值會是 0xffffffff

- `fix ^ (fix >> n)` 將 `fix` 與 `fix >> n` (0xffffffff 右移 n 位)做 XOR ，將右移的位元補 0

---

## 測驗 `2`
下方程式碼會在輸入為 4 的 n 次方時 ($4^n$) 回傳 `true` ，否則回傳 `false`

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

輸入為 4 的 n 次方時 ($4^n$) ，會有以下幾個特性 :
- num > 0
- (num & (num - 1))==0 : num 為 2 的 n 次方 ($2^n$)
ex: 10000000 & 01111111
- !(__builtin_ctz(num) & 0x1) : num 從右邊數來有偶數個 0 => num 為 4 的倍數

---

## 測驗 `3`
下方程式碼算出將輸入數字變成 0 需要多少步驟。而算法是：
- 若 `num` 為偶數，除以 2
- 若 `num` 為奇數，減 1

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

若以二進制來看 `num` ，可以將算法看成：
- 若 LSB 為 0 ，則向右移一位
- 若 LSB 為 1 ，則減一

則步驟數就可以分別看成：
- 將 MSB 移到最右側的步數 => `31 - __builtin_clz(num)`
- `num` 二進位 1 的數量 => `__builtin_popcount(num)`

---

## 測驗 `4`

#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 (v);
    return u << shift;
}

- 第 5 到 7 行等同於 $gcd(u,v) = 2gcd(\frac{u}{2},\frac{v}{2})$
- 8, 9 行與 11, 12 行都是把變數的 2 都除掉
- 14, 16 行則是輾轉相除法中最重要的一環，算出兩數的差
- 20 行則是判斷 v 是否為 0 ，也就是兩數是否相同
- 最後傳回剩下的值，並將剛剛除掉的 2 補回去

---

## 測驗 `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 = bitset & -bitset;
            int r = __builtin_ctzll(bitset);
            out[pos++] = k * 64 + r;
            bitset ^= t;                           
        }
    }
    return pos;
}

程式碼在第 8 行開始與 `naive` 有所不同， `naive` 利用 for 迴圈來一個一個位元檢查，而這裡是直接用 `ctz` 來計算，並將最右邊的 1 消除掉，因此使用 `bitset & -bitset`