# 2020q3 Homework4 (quiz4)
contributed by < [`OliveLake`](https://github.com/OliveLake) >
> [quiz4 題目描述](https://hackmd.io/@sysprog/2020-quiz4)

## Q1: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。

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

解題:
參數 x 和 y 作 `exclusive-or` 後，若兩者位元不同為 1 ，位元相同為 0，再利用 gcc 提供對應的內建函式：__builtin_popcount(x)，計算 x^y 總共有幾個 1 ，即為 Hamming Distance 。

#### 延伸問題:
1.不使用 gcc 實作

int hammingDistance(int x, int y){
    int i = x ^ y;
        int n = 0;
        while (i > 0)
        {
            if ((i & 1) == 1) n++;
            i >>= 1;
        }
        return n;
}

比起根據題目範圍做 31 次迴圈，先做 X^Y 可以知道哪些數字要計算距離，減少迴圈次數。再用```if ((i & 1) == 1) n++```計算每個位元的差。最後 i 再不斷右移，直到測資為零。

2.練習 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)

int totalHammingDistance(int* nums, int numsSize){
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int cnt = 0;
            for (int j = 0; j<numsSize; j++) {
                if (nums[j] & ((uint32_t)1 << i)) ++cnt;
            }
            ans += cnt * (numsSize - cnt);
        }
        return ans;
}

如果兩兩互取 Hamming Distance 的話，會因為測資有10000筆而超出時間。比較好的方法是，因為位元只有 0 和 1 兩種可能，從 LSB 開始分成為 0 的一堆，為 1 的一堆，分完算出距離再前進一位，這樣就只需要做 31 次迴圈( 31 個位元)，最後每個位元距離加總。
第 6 行 ```if (nums[j] & ((uint32_t)1 << i)) ++cnt;``` 判斷第 i 個位元是否為 1 。第 8 行 ```res += cnt * (n - cnt);``` 總合會是 0 的數量乘上 1 的數量。

舉例測資是 2(0010)、4 (0100)、14(1110)
| 位元 | 為 0 | 為 1 |距離
| -------- | -------- | -------- | -------- |
| 0 | 2、4、14 | X | 0
| 1 | 4 | 2、14 | 2
| 2 | 2 | 4、14 | 2
| 3 | 2、4 | 14 |2
距離總和是 6

參考 [RusselCK](https://hackmd.io/@RusselCK/sysprog2020_quiz4) 同學的寫法，改正

第 6 行```if (nums[j] & ((uint32_t)1 << i)) ++cnt;``` 為 ```cnt += nums[j] >> i & 1;```後，因為不需 if 判斷，速度可以再提升。

3.研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/上課講義/[20170710][抽象代數的實務應用].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說

## Q2:[LeetCode 1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/)

#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
由第 3 行開始的 struct 宣告及第 10 行的記憶體配置

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

型態是```TreeAncestor *```的 obj 指向 parent ，並且 parent 要了一段型態是```int *```的空間，因此 AAA 應為```int **parent```

### BBB