# 2020q3 Homework4 (quiz4)
contributed by < `StevenChen8759` >

###### tags: `linux2020`

> 相關連結：
> [2020秋季進階電腦系統理論與實作 quiz4](https://hackmd.io/@sysprog/2020-quiz4)
> [2020秋季進階電腦系統理論與實作 quiz4 作業說明](https://hackmd.io/@sysprog/r1z0WPWLD)
> [2020秋季進階電腦系統理論與實作 quiz4 作業繳交區](https://hackmd.io/@sysprog/2020-homework4)
> [color=green]

## :large_orange_diamond: 測驗一

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

### :building_construction: 程式碼分析
* 參考附圖中的雙立方體，可發現二進制表示中任兩個數字之間的 Hamming Distance 與表示法中對應位元不同的數量有關。
* `0110` 與 `0100` 之 Hamming Distance 為 1
* `0011` 與 `1100` 之 Hamming Distance 為 4
* 因此，我們需透過 XOR 指出位元表示不同的位置為 1，再以 `__builtin_popcount()` 計算位元為 1 的數量，即為輸入兩數的 Hamming Distance。
* 故 `OP` 應填入 `^`

## :large_orange_diamond: 測驗二

#include <stdlib.h>

typedef struct {
    AAA;
    int max_level;
} TreeAncestor;

TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
    TreeAncestor *obj = malloc(sizeof(TreeAncestor));
    obj->parent = malloc(n * sizeof(int *));

    int max_level = 32 - __builtin_clz(n) + 1;
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        for (int j = 0; j < max_level; j++)
            obj->parent[i][j] = -1;
    }
    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;
    }
    obj->max_level = max_level - 1;
    return obj;
}

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;
}

void treeAncestorFree(TreeAncestor *obj)
{
    for (int i = 0; i < obj->n; i++)
        free(obj->parent[i]);
    free(obj->parent);
    free(obj);
}

### :building_construction: 程式碼分析
* 觀察 `treeAncestorCreate()` 函式內部對 obj 的操作，在 allocate `n` 個 `int *` 型別的空間給 `obj->parent` 之後，再分配 `max_level` 個 `int` 的空間，並分別將其位址儲存在先前宣告的 `int *` 型別的記憶體位址之中。由這樣子的操作，可以知道 parent 是一個二維陣列，故其宣告應為指標的指標。
* 由上可知，`AAA` 應填入 `int **parent`。
* 觀察 `treeAncestorCreate()`，在第二個 for loop 時，程式將所有 node 的 parent 指派到配置的二維陣列之中；第三個 for loop 則是找出指定的節點是第幾代的 Ancestor。
* 觀察 25 行針對陣列元素的操作，可知 `BBB` 為了防止陣列輸入項為負值而造成錯誤，因此應填入 `-1`

## :large_orange_diamond: 測驗三

#define MSG_LEN 8

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
static uint64_t M5 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 5 + 1;

int main(int argc, char *argv[]) {
    for (size_t i = 1; i <= 100; i++) {
        uint8_t div3 = is_divisible(i, M3);
        uint8_t div5 = is_divisible(i, M5);
        unsigned int length = (2 << div3) << div5;

        char fmt[MSG_LEN + 1];
        strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);
        fmt[length] = '\0';

        printf(fmt, i);
        printf("\n");
    }
    return 0;
}

### :building_construction: 程式碼分析
* 根據 [quiz2](https://hackmd.io/@sysprog/2020-quiz2#%E6%B8%AC%E9%A9%97-4) 中測驗四所提，我們透過這個函式，得以較低的成本 (不需乘、除運算) 計算出一個數字 $n$ 是否可指定數字整除。
* 原理請參考 [quiz2 Homework 解說](https://hackmd.io/@StevenHHChen/linux2020q3_hw02_quiz2#-%E6%B8%AC%E9%A9%97%E5%9B%9B%E7%A8%8B%E5%BC%8F%E7%A2%BC%E8%88%87%E5%88%86%E6%9E%90)
* 根據上述提示，若 i 可被 3 整除，則 `div3` 的值為 1；若 i 可被 5 整除，則 `div5` 的值為 1
* 根據題意，在下列不同的狀況時，應輸出的字串對應如下:
* 1. 若 i 是 3 的倍數，但不是 5 的倍數，則印出 `Fizz`
* 2. 若 i 是 5 的倍數，但不是 3 的倍數，則印出 `Buzz`
* 3. 若 i 是 3 與 5 的倍數，則印出 `FizzBuzz`
* 4. 若 i 不是 3 與 5 的倍數，則印出 i 之值
* 觀察 `strncpy()` 陳述句，我們推敲出對應上述情況的輸出值與對應範圍
* ----------------------> (FizzBuzz%U\0)
* 1. start=0, length=4 (Fizz\0------)
* 2. start=4, length=4 (----Buzz\0--)
* 3. start=0, length=8 (FizzBuzz\0--)
* 4. start=8, length=2 (---------%u\0)
* 我們可以發現在第 4 種狀況時，字串仍然輸出並保留了可讓 `printf()` 可辨識的字元，這樣的設計可讓使用者輸出數字。
* length 之值已在第 14 行的程式碼計算出來，而接著需要探討的就是 start 值的問題了，我們根據 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 之 start 值與上述狀況加以分析 (已知 `MSG_LEN` 為 8)
* Case 1. 8 -> 0, Right Shift 4
* Case 2. 8 -> 4, Right Shift 1
* Case 3. 8 -> 0, Right Shift 4
* Case 4. 8 -> 8, Right Shift 0
* 根據上述的觀察，僅有在整除 5 時需右移 1 位元；而當一數可整除 3 時 (包含可同時整除 5)，則須右移 4 位元；並且在 3 跟 5 都不可整除時，右移位元數須為 0。
* 綜合以上的分析，`KK1` 應為 `div5`，`KK2` 應為 `div3`，`KK3` 應為 `2`，這樣的組合才可滿足要求。