# 2020q3 Homework4 (quiz4)
contribute by < `simpson0114` >
###### tags: `sysprog2020`

## 測驗 `1`

int hammingDistance(int x, int y) {
    return __builtin_popcount(x OP y);
}

因為 `__builtin_popcount` 會回傳二進位數中 1 的個數，因此要計算 `x` 和 `y` 二進位數中有哪些 bit 互補，因此答案為
OP =
>>`(c)` `^`

## 測驗 `2`

typedef struct {
    AAA;
    int max_level;
} TreeAncestor;

從 `treeAncestorCreate(int n, int *parent, int parentSize)` 這個 function 可以判斷 `parent` 為二維陣列，故
AAA =
>>`(b)` `int **parent`

for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

for (int j = 1;; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j + BBB] == -1
                                    ? -1
                                    : obj->parent[obj->parent[i][j - 1]][j - 1];
            if (obj->parent[i][j] != -1) quit = 0;
        }
        if (quit) break;
    }

因為在第一個 for 迴圈已經將每個 node 的 parent 都已經分配好了，所以在第二個 for 迴圈所需要做的工作是將每個 node 其他的 ancestor 都分配好，於是必須從要分配的 ancestor 的下一層 level 去找該層的 ancestor 是誰，故
BBB =
>>`(b)` `(-1)`

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    int max_level = obj->max_level;
    for (int i = 0; i < max_level && node != -1; ++i)
        if (k & (CCC))
            node = obj->parent[node][i];
    return node;
}

他的作法比較不直觀，假設 k = 3 ，它會先將 node 指派為 node 的 parent ，接下來進入下一個迴圈， `1 << 1` 會找到 node 的 parent 的 parent 。簡而言之，它就是一個 bit 一個 bit 處理，去找到對應的 parent 。
CCC =
>>`(e)` `1 << i`

## 測驗 `3`
本題主要是判斷是否整除 3 或 5 或 15 ，來決定輸出的內容。

strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);

看程式碼可知道主要是在控制字串的 start ，若可被 5 整除，則印出 Buzz ，因此 start = 4 (8 >> 1)，若可被 3 整除，則 start 為 0 ，因此至少要右移 4 (1 << 2)，故
KK1 =
>> `(a)` div5

KK2 =
>> `(d)` div3

KK3 =
>> `(c)` 2

## 測驗 `4`
本題題意是要減少除法運算的進行，因此在進行除法前先進行事先處理，避免不必要的除法運算。
而題目要探討有哪些 `CASES` 是必要的，而在題目給的程式碼可得知，在進行除法前，有先用 `__builtin_ffs()` 對除數與被除數進行 2 的倍數的處理，所以可得知 `CASES` 中不需處理 2 的倍數的除法，因此只需要 2 以外的質數除法便可，故
`CASES` 至少須包含
>>`(b)` 3
>>`(d)` 5
>>`(f)` 7