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