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

###### tags: `homework`

## 測驗 1

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

> population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1


###
- Hamming Distance 計算兩數之間相異 bit 個數，$x \oplus y$ 先將相異的 bit 位置設為 1 後再透過 __builtin_popcount 求出 1 的個數，即為 Hamming Distance
- 不使用 gcc extension 的 C99 實作程式碼

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


### LeetCode 477. Total Hamming Distance
- 暴力法

int totalHammingDistance(int* nums, int numsSize){
    int sum = 0;
    for(int i = 0; i < numsSize - 1; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            sum += __builtin_popcount(nums[i] ^ nums[j]);
        }
    }
    return sum;
}

先從較直覺的暴力法著手，numsSize 不斷增長的情況下，時間複雜度為 $O(n^2)$

- 觀察

| nums[i] | bit 3 | bit 2 | bit 1 | bit 0 |
| ------- | ------| ----- | ------| ----- |
| 4 | 0 | 0 | 0 | 1 |
| 14 | 1 | 1 | 1 | 0 |
| 2 | 0 | 0 | 1 | 0 |
| 1s | 1 | 2 | 2 | 0 |
| 0s | 2 | 1 | 1 | 3 |
| sum | 2 | 2 | 2 | 0 |

可以推得總和為所有資料中相對 bit 的 1 總數 * 0 總數，因此 $total sum = 1 \times 2 + 2 \times 1 + 2 \times 1 + 0 \times 3 = 6$

int* to_bit_array(int num) {
    int *bit_array = (int *) malloc(sizeof(int) * 32);
    memset(bit_array, 0, sizeof(int) * 32);

    for (int i = 0; i < 32; i++, num >>= 1)
        bit_array[i] += (num & 1);

    return bit_array;
}

void add_bit_array(int *a, int *b) {
    for (int i = 0; i < 32; i++)
        a[i] += b[i];
}

int totalHammingDistance(int* nums, int numsSize) {

    int sum = 0;

    int *bit_array = to_bit_array(0);

    for (int i = 0; i < numsSize; i++) {
        int *tmp = to_bit_array(nums[i]);
        add_bit_array(bit_array, tmp);
    }

    for (int i = 0; i < 32; i++)
        sum += bit_array[i] * (numsSize - bit_array[i]);

    return sum;
}

### 研讀錯誤更正碼簡介及抽象代數的實務應用
> 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源

**Hamming Distance & Hamming Weight**
- 定義
- Hamming Distance : 兩向量有幾個相異的 bit
> e.g. $x = (0001011), x' = (1101010), d_H(x,x') = 3$
- Hamming Weight : 一個向量不是 0 的的地方有幾個
> e.g. $w_H(x) = 3, w_H(x') = 4$
- x 和 x' 的 Hamming Distance 只是 (x + x') 的 Hamming Weight
- minimum distance : 在這個碼中，任兩不同 codewords 的 Hamming distance，其當中最小值
- minimum weight : 所有不為 0 的 codewords，其 Hamming weight 的最小值
- 特性
- 由於兩個 codewords 的 Hamming distance 會等於相加後的 Hamming weight，所以對線性碼來說，$d_{min(C)} = w_{min(C)}$，也就是 minimum distance 會等於 minimum weight
- 要改 t 個錯，其 minimum distance 至少要 $2t + 1$
> 1. 球心 (x, x') 為一個 codeword，球包含所有跟此 codeword 的 Hamming distance <= t 的 binary vectors
> 2. 由於要改 t 個錯，兩球不能交疊在一起，否則交疊的 vectors 不知道要改成 x 還是 x'
> 3. 因此兩球距離至少為 1，即任兩 codewords 距離至少要 $2t + 1$

### 研讀 Reed–Solomon error correction

---
## 測驗 2
>給你一棵樹，樹上有 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]]

Output:
[null,1,0,-1]

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

###

digraph treeAncestor {
    node[shape=record]

    node15 [label="{{<value> 15 | {<parent> 7 | 3 | 0 | -1 | -1 | -1}}}"]

    0 -> {1, 2}
    1 -> {3, 4}
    2 -> {5, 6}
    3 -> {7, 8}
    4 -> {9, 10}
    5 -> {11, 12}
    6 -> {13, 14}
    7 ->{node15, 16}
    8 -> {17, 18}
    9 -> {19, 20}
    10 -> {21, 22}
    11 -> {23, 24}
    12 -> {25, 26}
    13 -> {27, 28}
    14 -> {29, 30}
}

treeAncestorCreate

- ```#11 obj->parent = malloc(n * sizeof(int *)); ``` 從這行可以知道結構體成員 parent 為 a pointer to a pointer，故 AAA 為 int ** parent
- ```#13 int max_level = 32 - __builtin_clz(n) + 1;``` 計算最大樹高 (skewed)
- ```
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;
}

    初始化 obj ，index i 表示節點編號，index j 存取**上 $2^{j}$ 代祖先**，因此 ```obj->parent[i][j] = -1;``` 先將每個節點的**每 $2^{j}$ 代祖先**設為 -1 (沒有祖先)
- ```
   for (int i = 0; i < parentSize; i++)
    obj->parent[i][0] = parent[i]; 

每個節點的上一代 ( j = 0 ) 祖先根據給定的 parent 序列逐一指派，例如 parent 給定 [-1,0,0,1,1,2,2]，則第 0 個節點的上一代祖先將被指派為 -1
- ```
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;
}

     接著建立**上 $2^{j}$ 代祖先**，j 從 1 開始，當存在**上 $2^{j-1}$ 代祖先**時，才會有**上 $2^{j}$ 代祖先**，因此 BBB = -1

treeAncestorGetKthAncestor

- 搜尋**上 k 代祖先**，如果**上 $2^i$ 代祖先存在**，就從上 $2^i$ 代祖先繼續往上搜尋
- 例如 k = 5 (0b101)，則 i 在 0、2 時可能會有上 $2^i$ 代祖先存在，如果上 $2^0$ 代祖先存在，則從上一代祖先繼續往上搜尋上 $2^2$ 祖先


### 

---
## 測驗 3

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

> 從 1 數到 n，
如果是 3的倍數，印出 “Fizz”
如果是 5 的倍數，印出 “Buzz”
如果是 15 的倍數，印出 “FizzBuzz”
如果都不是，就印出數字本身

###
- 從 ```strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);``` 可以回推程式想執行的事情
    - 從 "FizzBuzz%u" 中取出特定長度的字串出來放到變數 fmt，再將其打印出來
    - 而要取多長則取決於變數 length，從哪裡開始取則取決於 (MSG_LEN >> KK1) >> (KK2 << KK3) ，其中 MSG_LEN 8
- ```unsigned int length = (2 << div3) << div5;```
    - 從 1 數到 n ，如果可以被 3 整除則 div3 將被設成 1，否則為 0 ，同理 div 5
    - 因此我們會得到下列四種不同的 length
        - 3 的倍數，(2 << 1) << 0 得 4
        - 5 的倍數，(2 << 0) << 1 得 4 
        - 15 的倍數，(2 << 1) << 1 得 8
        - 都不是，(2 << 0) << 0 得 2
- ```(MSG_LEN >> KK1) >> (KK2 << KK3)``` 根據以上不同的情境將未知的 KK 填入
    - 先考慮 3 和 15 的倍數，要印出 “Fizz” 和 “FizzBuzz” 都得從字串的 0 位開始取，先從選項中取固定常數出來嘗試
        - KK1 = 1、KK2 = 2、KK3 = 2，可得 0
    - 接著考慮 5 的倍數，要印出 “Buzz” 得從字串的 4 位開始取
        - 將 KK2 改成 div3 可得 4
    - 而最後考慮都不是的情況，要取得字串的輸出控制符 %u 得從字串的 8 位開始取
        - 最後將 KK1 改成 div5 可得 8

---
## 測驗 4
> 考慮到整數 PAGE_QUEUES 可能有以下數值:
> (1 or 2 or 3 or 4)
> (5 or 6 or 7 or 8) × ($2^n$), n from 1 to 14

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

其中 CASES 可能形如:

case 2: blockidx /= 2;
break;

用最少的 case-break 敘述做出同等 ```size_t blockidx = offset / PAGE_QUEUES;``` 效果的程式碼

- ```__builtin_ffs(x))``` 表示 x 二進位中最後一個 1 的位置
> int __builtin_ffs (unsigned int x)
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
- ``` ffs32(x)  ((__builtin_ffs(x)) - 1)``` 等同於 ctz ，表示尾端有幾個 0，即該數是否含有 $2^n$
- ```blockidx = offset >> ffs32(divident);``` $offset /= 2^n$，先從 offset 提出 $2^n$
- ```divident >>= ffs32(divident);``` $divident /= 2^n$
- 將 $2^n$ 提出後且 PAGE_QUEUES 最多為 $8 \times 2^n$，故只需判斷 ```blockidx /= y```，y = 2, 3, 5, 7 質數即可
---