# 2020q3 Homework4 (quiz4)
contributed by < `jonec76` >
###### tags: `sysprog-2020`

> [作業說明](https://hackmd.io/@sysprog/r1z0WPWLD)
> [題目](https://hackmd.io/@sysprog/2020-quiz4)

## 開發環境

$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux

## 參考解答

OP = ^
AAA = int **
BBB = -1
CCC = 1 << i
KK1 = div5
KK2 = div3
KK3 = 2

## Q1

- 解題想法

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

可以先觀察一下圖上的點，如果兩點之間 bit 中只有 1 位不相同的話，那可以知道兩個點的距離只差 1。根據這個原則，只要找出兩個數字有多少個 bit 不同即可。

那如何找出呢？這邊可以使用 XOR 找出，因為 XOR 的特性剛好可以使不同 bit （`0^1`）出來的結果是 1，若是相同的話就會變成 0。

接著，再使用 `__builtin_popcount` 計算出有多少個 1，即可知道答案了。

## Q2

- 解題方向

在解 AAA 時，可以從下方這行程式碼得出

    obj->parent = malloc(n * sizeof(int *));

表示 `obj->parent` 是個具有 n 個 `int *` 的 pointer，如此即可知道應為 `int **` 型態。

在解 BBB 之前，可以先了解此題題目目的，參考下方程式碼

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

找出 `max_level` 的方法蠻有趣的，背後含義是做了 $\lfloor log\ n\rfloor$。一開始想說應該是想要找出 n 最大會在哪個 level，但是！之後再看一次題目才知道不是這樣子（需要配合 `treeAncestorGetKthAncestor` 來看）

這邊就是建立每個點的 parent table，用來記錄該點之上的 "幾個" parent（不是所有都紀錄！），並且對每個 node 的 parent table 做初始化。

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

接著可以看到下方 BBB 的填空

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

若是倒著推回來的話，可以先思考一下怎樣的情況，parent 會是 `-1`？

同時，又可以看到需要根據該點之外的其他 parent ，來更新目前的 parent。此時就可以推測出，如果在 `j - 1` 已經是 `-1`，也就是沒有任何 node 在 `j - 1` 之上，那 `j` 一定也不會有 parent。

接著，看到最後 CCC 選項

    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 個 parent。當初看到此題時，想說就是 n 往上數到第 k 個 node 並且回傳。但事實上並非如此，以下圖為例子

    digraph skew_BST {
        size="10,3!" 
        node [fontname="Arial"];
        0 -> 1;
        1 -> 2;
        2 -> 3;
        3 -> 4;
        4 -> 5;
        5 -> 6;
    }

以例子來看，在 node 6 的 parent table 應為下圖，parent[i] 紀錄的是往上數第 $2^i$ 個點

    digraph hash_table {
        nodesep = .05;
        rankdir = LR;

        node[shape = record, width = .1, height = .1];

        node0[label = "<f9> 6", height = 0.5];

        node [width = 1.5];

        node9[label = "{ 5|4|2}"];

        node0:f9 -> node9;
    }

why? 由下方程式碼可以看出

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

以 `parent[5][2]` (node 6) 來看，那就會被更新為 `parent[4][1]` (node 5)。
以 `parent[5][3]` (node 6) 來看，那就會被更新為 `parent[3][2]` (node 4)。

這樣的紀錄方法，將會使得 `parent[i]` 紀錄的是往上數第 $2^i$ 個點。對於這樣設計的原因，自己思考後是認為這樣的設計能夠處理 balanced tree，也能處理 skew tree，不需要因為 tree 的高度而變動 parent table size，反而只要知道 node 總數即可。

既然如此，再回到 CCC 選項。若 node=6, k=5 時，也就是要找出 node=6 往上數第 5 個的 node。這邊以 `treeAncestorGetKthAncestor` 來看，跑法會是
1. 取出 node 6 的第 $2^0$ parent，也就是 5
2. 5 再取出第 $2^2$ 點，也就是 0

打破原先那直觀的觀念（往上走 5 步），而是用走 "2 的冪次方" 的方法取點。

## Q3

- 程式碼分析

    if (i % 3 == 0) printf("Fizz");
    if (i % 5 == 0) printf("Buzz");
    if (i % 15 == 0) printf("FizzBuzz");
    if ((i % 3) && (i % 5)) printf("%u", i);

此題的原意其實很簡單，目的就是根據以上的程式碼印出。

接著此題希望使用 `strncpy` 的方式，來複製出原始字串的 substring。複製的參數是

1. start 字串的起始位置
2. 複製的長度

複製程式碼如下：

    #define MSG_LEN 8
    char fmt[MSG_LEN + 1];
    strncpy(fmt, &"FizzBuzz%u"[start], length);
    fmt[length] = '\0';
    printf(fmt, i);
    printf("\n");

- 解題想法

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

此題基本上就是要把數字湊出來，在 [quiz2-Q4](https://hackmd.io/@jonec76/2020q3-quiz2#Q4) 中分析過 `is_divisible` 的原理。所以可以知道此題的 `div3` 、 `div5` 就會表示出目前的數可否被相對 `3` 或 `5` 整除，可以的話就得 `1`，否則 `0`。

以下為 output 合併 `strncpy` 參數的 table：
|value|output|start index|length|
|---|---|---|---|---|
|n 整除 3|"Fizz"|0|4|
|n 整除 5|"Buzz"|4|4|
|n 整除 15|"FizzBuzz"|0|8|
|以上皆非|n|0|0|

湊了幾組後即可得到答案。

這邊在課堂上寫的時候發生了粗心的情況，順便記錄一下。當時把 `div3 << 2` 跟 `2 << div3` 寫相反，當 `div3=1` 時的確值是一樣，但是缺少考慮了 `div3=0` 的 case。