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

## 測驗 1
LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 `1` 的二進位為 `0 0 0 1`，而整數 `4` 的二進位為 `0 1 0 0`，則 `1` 與 `4 `的 Hamming distance 為 `2`。

1   (0  0  0  1)
4   (0  1  0  0)
       [ ]   [ ]
        |     |
        \_ 2 _/

上圖 [hypercube](https://en.wikipedia.org/wiki/Hypercube) (中文翻譯：超方形) 中，紅色路徑的 0100 到 1001 的 Hamming distance 為 3，而藍色路徑的 0110 到 1110 的 Hamming distance 則是 1。

運用[第 3 周測驗](https://hackmd.io/@sysprog/2020-quiz3) 提到的 __builtin_popcount (gcc extension 之一)，我們可實作如下:

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

* OP = `^`
* 由上述 hamming code 定義可知兩個整數的 Hamming distance 為`其二進位的每個位元的差`，而 `x ^ y` 操作的結果為兩數某位不同則該位為 1，否則該位為 0
*
* 由此可知 `x` 與 `y` 的 Hamming distance 為 `__builtin_popcount(x ^ y)`

:::success
延伸問題:

1. 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼;
2. 練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
3. 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
* 搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
4. 研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
:::

## 測驗 2
LeetCode 1483. Kth Ancestor of a Tree Node 大意:
>給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 `parent[i]` 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 `treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)` 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 `-1`。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點

Input:

["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

:::info
:information_source: 上方為 JSON 格式，其中:
7 表示共有 7 個節點
GetKthAncestor(3, 1) 預期回傳 1，後者是 3 的父節點，即「上 1 代」;
GetKthAncestor(5, 2) 預期回傳 0，後者是 5 的祖父節點，即「上 2 代」;
GetKthAncestor(6, 3) 預期回傳 -1，因為不存在這樣的節點
:::
Output:

[null,1,0,-1]

以下是參考 C 程式實作:

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

* AAA = `int **parent`
由 Line 11 `obj->parent = malloc(n * sizeof(int *));` 可知 `parent` 是一個 pointer to pointer to int
* BBB =
* CCC =
## 測驗 3

## 測驗 4