# 2020q3 Homework4 (quiz4)
contributed by `joey3639570`
###### tags: `進階電腦系統理論與實作`
## 測驗 `1`

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

### 延伸問題:

>解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼;

hammingDistance 要找出有幾個位元的不同，`__builtin_popcount` 用於找出有幾個位元的 `1` ， 利用`x ^ y` 能找出位元值不同者，以下面例子而言:

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

`0001` ^ `1000` = `1001`
`__builtin_popcount(1001)` = **2**

答案: `OP` 為 `^`

#### 不使用 GCC Extension
主要避免使用的部分為 `__builtin_popcount()`
參考: [Bits Twiddling Hacks : Counting bits set, Brian Kernighan's way](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)

int hammingDistance(int x, int y) {
    int res, n;
    n = x ^ y;
    for (res = 0; n; n &= n-1) {
        res++;
    }
    return res;
}

利用 `n &= n-1` 清除對 the least significant bit set，此方法有機會比直覺的方法(純迴圈)快，仍有用到分支，仍有改善空間。

>練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
### 題目解說:
>Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

### 直覺方法:

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

int totalHammingDistance(int* nums, int numsSize){
    int i = 0;
    int j;
    int result = 0;
    for (i ; i < numsSize; i++) {
        for (j = i + 1; j < numsSize; j++) {
            result += hammingDistance(nums[i], nums[j]);
        }
    }
    return result;
}

果不其然，超時

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

>研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。

## 測驗 `2`

#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` 可以 `obj->parent = malloc(n * sizeof(int *));` 推論出來，其對於 `obj->parent` 分配了 n 個 `int *` 的空間，這表示 parent 為這些指標們的指標，故 `AAA` 為 `int **parent`

在此可以先了解 `TreeAncestor` 的結構:
- `int **parent` : 可以參考題目解釋，如下
>給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。
- `max_level` : 記錄著總共有幾層的樹

`treeAncestorCreate` :
1. 先 malloc 出 `TreeAncestor` 及 `obj->parent` 的記憶體空間
2. 設置 `max_level` 為 `32 - __builtin_clz(n) + 1` ，共 32 位元的狀況下，減掉 leading zero 能得到 Binary Tree 的共有幾層。以 `N` 為 15 (1111) 為例，第一層有 $2^0$ 個， 第二層有 $2^1$ 個，第三層有 $2^2$ 個，第四層有 $2^3$ 個， `32 - __builtin_clz(n) + 1` 為 `32 - 28 + 1` 可以參考下圖 :

digraph G {
    a [label="0"]
    b [label="1"]
    c [label="2"]
    d [label="3"]
    e [label="4"]
    f [label="5"]
    g [label="6"];
    h [label="7"];
    i [label="8"];
    j [label="9"];
    k [label="10"];
    l [label="11"];
    m [label="12"];
    n [label="13"];
    o [label="14"];
    
    a->b;a->c;
    b->d;b->e;c->f;c->g;
    d->h;d->i;e->j;e->k;
    f->l;f->m;g->n;g->o;

  labelloc="t";
  label="My Graph";
}

3. 接下的 for 迴圈，會對於每個 `obj->parent[i]` 分配 `max_level` 個 `int` 的空間，並且初始化這些數值為 -1
4. 下一個 for 迴圈，會對於每個 `obj->parent[i]` 的第 0 個設為 `parent[i]` ，也就是該節點自己本身
5. 再下一個 for 迴圈，利用一 flag `quit` 為迴圈終止條件，藉此建立每個節點的 ancestor 關係
6. 最後 `obj->max_level = max_level - 1`，再把前面多的減一弄回來
:::info
待辦:
- 為何 max_level 一開始 要加 1 ? (``32 - __builtin_clz(n) + 1``)
> 程式碼是寫給你改進的，裡頭故意留下一些缺失，遇到疑慮就大膽假設小心求證
> :notes: jserv
:::

`treeAncestorGetKthAncestor` :
直接探討到 for 迴圈:
- 在 i 未到達 `max_level` 且 node <s>本身有被賦予值</s> 已指定數值，迴圈持續進行，找到正確的階層 (k) ，便會指派 ` obj->parent[node][i]` 給 `node`

:::warning
"assignment" 應依據文意翻譯，若書寫為「賦值」往往會詞語不通順
:notes: jserv
:::

>在 treeAncestorCreate 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;

>在 LeetCode 1483. Kth Ancestor of a Tree Node 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;

## 測驗 `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;
}

### 延伸問題:
>解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
> - 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf

- `is_divisible` 及 `M3` 及 `M5` 這部分可以回歸到 quiz2 的測驗 `4` 參考
- `length` 是要 print 出的字串長度，共有以下這幾個可能 :
- `FizzBuzz` : 8
- `Fizz` 及 `Buzz` : 4
- print 數字的狀況下， `length` 會被設為 2，這是整數格式字串 `"%d"` 的長度
- `fmt[MSG_LEN + 1]` 要注意字串有 `'\0'` ，所以要 +1
- 以四種字串可能探討 `strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);`
- 先以下方表格整理字串狀況及對應的變數 :

| 字串 | 開始 Index | div3 | div5 |
|:---------- |:----------:|:----:|:----:|
| `FizzBuzz` | 0 | 1 | 1 |
| `Fizz` | 0 | 1 | 0 |
| `Buzz` | 4 | 0 | 1 |
| 數字 | 8 | 0 | 0 |
綜合上面判斷 `KK1` `KK2` `KK3` :
- `KK1` : 使 Index 有 8 及 4 的可能，倘若只有用到 `KK1` ，字串會是 `Buzz` ，由此推論是 `div5`
- `KK2` 及 `KK3` : 這兩個要一起看，當需要 print 出數字時， Index 要保留為 8 ， 故 `KK2 << KK3` 要為 0 ，綜合 print `Buzz` 和數字的 Case 推出 `KK2` 為 `div3` ， `KK3` 為 `2`
- 最後要把字串的尾端放上 `'\0'`

>評估 `naive.c` 和 `bitwise.c`
`naive.c`

#include <stdio.h>
int main() {
    for (unsigned int i = 1; i < 100; i++) {
        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);
        printf("\n");
    }
    return 0;
}

- 首先較顯而易見的是這 `bitwise.c` 大幅減少了分支的使用，這於先前我的[作業 2](https://hackmd.io/@joey3639570/Hkoajm0Vw)有提過減少分支的影響及資安問題
:::info
待辦:
- 效能評估
:::

>分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware

## 測驗 `4`

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

### 延伸問題:
>解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;
對應的原始程式碼 src/mem/sizeclass.h

>練習 LeetCode 51. N-Queens，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;