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

## 程式運作原理
### 測驗一

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

根據題目提及，兩個數的 Hamming distance 其實就是其二進位表示中，相應位置數值不同的 bit 個數。
以 `1` 與 `4` 為例：

1   (0  0  0  1)
4   (0  1  0  0)
        ｜    ｜
      [相異] [相異]

有兩個位置的值不同，故 `1` 與 `4` 的 Hamming distance 為 2。
因此，對兩數使用 bitwise XOR 運算後，計算二進位表示中 1 的數目，即可求得兩數間的 Hamming distance。
### 測驗二

#include <stdlib.h>

typedef struct {
    int **parent/*AAA*/;
    int max_level;
    int n;
} TreeAncestor;

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

    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 + (-1)/*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 & (1 << i/*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);
}

為方便說明，我們以下面這個 tree 為例：

digraph skew_BST {
    node [fontname="Arial"];
    0 -> 1;
    1 -> 2;
    2 -> 3;
    3 -> 4;
    4 -> 5;
    5 -> 6;
    6 -> 7;
    7 -> 8;
    8 -> 9;
}

對 `parent` 中每一個 pointer to integer 指向的記憶體空間的內容初始化後，資料結構中的內容如下：

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

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

    node0[label = "<f0> int *|<f1> |<f2> |<f3> |<f4> |<f5> int *|<f6> |<f7> |<f8> |<f9> int *", height = 3.5];

    node [width = 1.5];

    node1[label = "{ -1|-1|-1|-1|-1}"];
    node5[label = "{ -1|-1|-1|-1|-1}"];
    node9[label = "{ -1|-1|-1|-1|-1}"];


    node0:f0 -> node1;
    node0:f5 -> node5;
    node0:f9 -> node9;


}

接著在 `parent[i][0]` 中填入第 i 個數的第一個 parent：

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

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

    node0[label = "<f0> int *|<f1> |<f2> |<f3> |<f4> |<f5> int *|<f6> |<f7> |<f8> |<f9> int *", height = 3.5];

    node [width = 1.5];

    node1[label = "{ -1|-1|-1|-1|-1}"];
    node5[label = "{ 4|-1|-1|-1|-1}"];
    node9[label = "{ 8|-1|-1|-1|-1}"];


    node0:f0 -> node1;
    node0:f5 -> node5;
    node0:f9 -> node9;


}

依照程式碼

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

最後資料結構的內容會變成這樣：

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

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

    node0[label = "<f0> int *|<f1> |<f2> |<f3> |<f4> |<f5> int *|<f6> |<f7> |<f8> |<f9> int *", height = 3.5];

    node [width = 1.5];

    node1[label = "{ -1|-1|-1|-1|-1}"];
    node5[label = "{ 4|3|1|-1|-1}"];
    node9[label = "{ 8|7|5|1|-1}"];


    node0:f0 -> node1;
    node0:f5 -> node5;
    node0:f9 -> node9;


}

用表格分析會清楚一點：

|i \\ j|0|1|2|3|4|
|-|-|-|-|-|-|
|0|-1|-1|-1|-1|-1|
|1|0|-1|-1|-1|-1|
|2|1|0|-1|-1|-1|
|3|2|1|-1|-1|-1|
|4|3|2|0|-1|-1|
|5|4|3|1|-1|-1|
|6|5|4|2|-1|-1|
|7|6|5|3|-1|-1|
|8|7|6|4|0|-1|
|9|8|7|5|1|-1|

可以觀察到， `parent[i][j]` 代表第 i 個數的第 $2^j$ 個 ancestor。
於是，在尋找數字 `node` 的第 `k` 個 ancestor 時，以 `node` = 9 , `k` = 7 為例，我們可以這麼想：
`k` 的 2 進位表示為 $0111 = 0100 + 0010 + 0001$，
`node = 9` 的第 `0001` 個 ancestor 為 8;
`node = 8` 的第 `0010` 個 ancestor 為 6;
`node = 6` 的第 `0100` 個 ancestor 為 2;
故得 `node = 9` 的第 `7` 個 ancestor 為2。
這些想法對應到程式碼：

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 & (1 << i/*CCC*/))
            node = obj->parent[node][i];
    return node;
}

### 測驗三

#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 >> div5/*KK1*/) >> (div3/*KK2*/ << 2/*KK3*/)], length);
        fmt[length] = '\0';

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

這題的關鍵，是透過 input number 性質控制從格式化字符串 `"FizzBuzz%u"` 的何處開始印起、總共印多少個字符。
我們可以透過表格分析這三者間的關係：
|在字符串中的相對位置|印的字符量|input number 性質|
|-|-|-|
|0|4|divisible by 3|
|4|4|divisible by 5|
|0|8|divisible by 3 and 5|
|8|2|not divisible by 3 and 5|

可以把表格分拆成兩部份：
|在字符串中的相對位置|印的字符量|input number 性質|
|-|-|-|
|0|4|divisible by 3|
|8|2|not divisible by 3|

可以寫成`(8 >> (div3 << 2))`

|在字符串中的相對位置|印的字符量|input number 性質|
|-|-|-|
|4|4|divisible by 5|
|8|2|not divisible by 5|

可以寫成`(8 >> (div5))`

兩者合併後，可以寫成 `((8 >> div5) >> (div3 << 3))`，此即為所求。
### 測驗四

#include <stdint.h>
#define ffs32(x)  ((__builtin_ffs(x)) - 1)
size_t blockidx;
size_t divident = PAGE_QUEUES;
blockidx = offset >> ffs32(divident);
divident >>= ffs32(divident);
switch (divident) {
    CASES
}

這裡要分析至少需要分成幾種 case 才能涵蓋所有 `offset / PAGE_QUEUES` 會遇到的情況。
這裡要先說明我們能不用除法指令的其中原理：
以 $7\cdot2^n ,n \space from\space 1\space to\space 14$ 為例，我們可以寫成$(111{\overbrace{000...000}^{n 個 0}})_2$，拆成$(111)_2\cdot({1\overbrace{000...000}^{n 個 0}})_2$。我們做除法時可以先除以 $({1\overbrace{000...000}^{n 個 0}})_2$ 這塊，接著再除以 $(111)_2$ ，步驟如下：
1. 首先是 $({1\overbrace{000...000}^{n 個 0}})_2$，我們透過 `ffs32(x)` 算出 n ，先計算 `offset >> n`。
2. 接著計算 $(111{\overbrace{000...000}^{n 個 0}})_2$ >> n，算出 $(111)_2$ 。
3. 最後計算 $(offset\space{>>}\space n)/(111)_2$ ，或是作其他處理。

可以看到從 `2.`開始分出了case。對於給定的集合，我們可以分析出如下 case:
|case|數字|數字(2進位表示)|
|-|-|-|
|1|1$\cdot2^n$|1$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|2|2$\cdot2^n$|10$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|3|3$\cdot2^n$|11$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|4|4$\cdot2^n$|100$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|5|5$\cdot2^n$|101$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|6|6$\cdot2^n$|110$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|7|7$\cdot2^n$|111$\cdot{1\overbrace{000...000}^{n 個 0}}$|
|8|8$\cdot2^n$|1000$\cdot{1\overbrace{000...000}^{n 個 0}}$|
case 1、2、4、8 只須做 shift 運算，不會進到最後的除法操作，所以要處理的 case 只有 `3、5、7`。