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

## 目錄
[TOC]

## 測驗 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。

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

請補完程式碼。
### 作答
這邊運用 xor 就可以找到哪些位元是不相同的，最後在使用 `__builtin_popcount` 就可以得到 Hamming distance，所以 OP = `^`。

### 延伸問題

#### 題目
練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時

#### 作答
稍微觀察一下下表就可以發現，只要看第 n 個位置的 bit 總共有幾個 0 跟 1，一對 0 跟 1 就會有一個 hamming distance，所以最後我們只要找出第 n 個 bit 有幾個 1 跟 0 就可以計算出 hamming distance。

| decimal | bit 2 | bit 1 | bit 0|
| -------- | -------- | -------- | -------- |
| 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 |

實作方式如下，用 `bit_count` 的陣列紀錄每個 bit 1 出現的次數，第 5 行的 while 迴圈則是運用作業 3 的技巧去找到當中是 1 的 bit 位置並記錄到 `bit_count`，最後的 for 迴圈則是計算出每個位元的 hamming distance。

int totalHammingDistance(int* nums, int numsSize){
    int bit_count[sizeof(int) * 8] = {0};
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];
        while (num) {
            bit_count[__builtin_ctz(num)]++;
            num ^= num & -num;
        }
    }
    int sum = 0;
    for (int i = 0; i < sizeof(int) * 8; i++) {
        sum += (numsSize - bit_count[i]) * bit_count[i];
    }
    return sum;
}

提交到 Leetcode 上的結果。

:::info
TODO
- 研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
- 研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
:::

## 測驗 2
### 題目
LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/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 個節點


以下是參考 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);
}

請補完。

### 作答
範例當中 `[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]`，第一個陣列的 7 代表 7 個節點，後面的陣列則是代表每個節點的 ancestor 是誰。再來這題並沒有說到這個 tree 是 binary 或是 full、complete tree，所以都是有可能的。

因此一個節點最多有可能會有 n-1 個 ancestor。如果一個一個找起了話時間是複雜度是 $O(n)$ 空間複雜度也是 $O(n)$，那如果在建樹的時候把所有的 ancestor 都用表紀錄下來，那查尋的時間複雜度就是 $O(1)$ 但是空間複雜度就是 $O(n^2)$，這邊題目為了取得一個平衡，所以選擇記錄下每個節點的 $\lfloor{log_2{n}}\rfloor+1$ 的祖先，那在空間上我們就只需要花 $O(n{log{n}})$，在查詢的時間複雜度是 $O(logn)$。

再探討一下這個方法，為何只要記錄下每個節點的 $\lfloor{log_2{n}}\rfloor+1$ 祖先，就保證能找到所有的祖先，那這邊要先知道一件事情，假設我們今天要找某個節點的第 k 個祖先，可以替換成某個節點的第 1 個祖先的第 k-1 個祖先，或是第 2 個祖先的第 k-2 個祖先，以此類推。所以第一個條件，不能去找某個節點大於 $\lfloor{log_2{n}}\rfloor+1$ 的祖先。

再來要怎麼確定再這樣的條件下一定可以找到所有的祖先，那就是本題的方法，從二進位的角度來想，假設 5 可以寫成，$2^2+2^0$ 這樣的表示，那我們今天要找某一個節點的第 5 個祖先，就可以換成找第 $2^0$ 個祖先的第 $2^2$ 個祖先，那今天要找第 n 個祖先，這樣我們最多就只會找到第 $\lfloor{log_2{n}}\rfloor+1$ 個祖先，就可以滿足第一個條件，並且可以在時間複雜度 $O(logn)$ 下面完成。接下來看到程式碼。

第 11 行可以看到先配置了 n 個節點的大小，可以知道 TreeAncestor 裡面的 AAA 是一個二維的資料結構，所以是 `**parent`。
第 13 行變數 `max_level = 32 - __builtin_clz(n)` 就是 $\lfloor{log_2{n}}\rfloor+1$，但是這邊 `32 - __builtin_clz(n)` 還多加了一個 1，後面會提到。
第 14 行的迴圈則在初始化，第 19 行是先記錄下每個節點的第一個 ancestor。
第 25 行是把每個節點的 ancestor 記錄下來，所以 `obj->parent[i][j + BBB] == -1` 先判斷上一個祖先是不是 -1，不是的話就把去找到這個祖先記錄下來。

第 36 行 treeAncestorGetKthAncestor 這個是找到第 k 個 ancestor，迴圈的中止條件就是已經找到 -1 代表不存在，或是大於等於 max_level。第 40 行這邊就是我們上面講的方法，對二進為每個 bit 去做替換，假設找某一個節點的第 5 個祖先，5 的二進為是 `101`，就可以換成找第 $2^0$ 個祖先的第 $2^2$ 個祖先，所以 CCC 就是 `1 << i`，從最低位的開始替換。

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

#### 作答
剛剛上面有提到第 13 行變數 `max_level = 32 - __builtin_clz(n)` 就是 $\lfloor{log_2{n}}\rfloor+1$，但是這邊 `32 - __builtin_clz(n)` 還多加了一個 1，透過剛剛的解題思維，給定第 k 個祖先，我們最大只會用到第 $\lfloor{log_2{k}}\rfloor+1$ 個位元，所以這邊不需要 +1，節省記憶體的空間。

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

#### 作答
在改進過程當中發現 leetcode 繳交同一份程式的時間會有些落差，連 memory 的使用也會有小誤差，所以以下都是繳交數次截圖比較優的一次，作為參考。

##### treeAncestorCreate

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

    int max_level = 32 - __builtin_clz(n);
    for (int i = 0; i < n; i++) {
        obj->parent[i] = malloc(max_level * sizeof(int));
        memset(obj->parent[i], -1, max_level * sizeof(int));
    }
    for (int i = 0; i < parentSize; i++)
        obj->parent[i][0] = parent[i];

    for (int j = 1; j < max_level; j++) {
        int quit = 1;
        for (int i = 0; i < parentSize; i++) {
            obj->parent[i][j] = obj->parent[i][j - 1] == -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;
    return obj;
}

這邊的修改就是把 max_level 的 +1 拿掉，然後第 15 行的 for 迴圈要加上終止條件 `j < max_level`。
第 10 行原本的 for 迴圈改以 memset 進行初始化。

##### treeAncestorGetKthAncestor

int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
    while (k && node != -1) {
        node = obj->parent[node][__builtin_ctz(k)];
        k ^= k & -k;
    }
    return node;
}

查詢第 k 個祖先這邊原本是從最低位元一個一個開始找起，找到 1 的 bit 就做替換，那這個也可以換成上一個作業的技巧，透過 `__builtin_ctz` 直接找到最低位為 1 的位元，所以這邊改用 while 迴圈，中止條件多了一個 `k == 0`。

不過這裡應該要對 k 的大小進行判斷，仔細觀察發現原本的程式也沒有進行判斷，如果今天 k 給一個大於 max_level 的值，然後剛好是 2 的次方這個方法就會噴錯，於是自己寫了程式跑了一下驗證，果然是會有錯誤的，詳細的 code 放在 [Github](https://github.com/Holychung/2020q3_System_Software/blob/main/quiz4/getKthAncestor.c)，神奇的是 leetcode 都通過了:confused:。

- 原版
- 
- `max_level` 修正 -1
- 
- treeAncestorGetKthAncestor 改用 ctz 作法
- 
- 改用 memset 初始化(以下是同一份程式兩次繳交，時間跟空間大小都有落差:confused: )
- 
- 

## 測驗 3
### 題目
出處: [簡單的 FizzBuzz 藏有深度 (Google 面試題)](https://medium.com/@Bear_/%E7%B0%A1%E5%96%AE%E7%9A%84-fizzbuzz-%E8%97%8F%E6%9C%89-%E6%B7%B1%E5%BA%A6-google-%E9%9D%A2%E8%A9%A6%E9%A1%8C-f5e66e3a97be)

考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:

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

我們若能精準從給定輸入 i 的規律去控制 start 及 length，即可符合 FizzBuzz 題意:

 string literal: "fizzbuzz%u"
         offset:  0   4   8

以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (bitwise.c)

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

請補完。

### 作答
這題判斷是否能整除有用到 [作業二 quickmod](https://hackmd.io/NyQg-me_SlCYj_PUMkGi8Q#%E6%B8%AC%E9%A9%97-3) 的技巧來判斷是否能整除，並且透過精準地控制 start、length，即可正確的輸出。

第 14 行可以看到 length 原本是 2，如果能整除 3 或 5 就往右邊 shift 一位，也就是乘二的意思，兩個都能整除就 shift 兩次，得到 8。

接下來看到 17 行要控制 string literal `"FizzBuzz%u"` 的 start 位置，於是用下表觀察一下。

| div3 | div5 | length | start |
| -------- | -------- | -------- | -------- |
| 0 | 0 | 2 | 8 |
| 1 | 0 | 4 | 0 |
| 0 | 1 | 4 | 4 |
| 1 | 1 | 8 | 0 |

這邊觀察 div3、div5、start 三個變數，在 div3 = 1 的時候 start 都要為 0，所以可以知道 `KK2 << KK3` 這邊應該是 `div3 << 2` 這樣就會把前面歸 0。剩下的推倒一下就可以得到 KK1 = `div5`。

### 延伸問題
評估 naive.c 和 bitwise.c 效能落差
避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf

#### 作答
這邊要記得將所有的 printf 換成 sprintf，不然會大大影響實驗的結果，測試從 1 到 100000，並且重複執行 100 次，進行觀察。

##### `cmp_fizzBuzz.c`

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <string.h>
#include <time.h>

#define TEST_RANGE 100000
#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[]) {
    long long time1 = 0LL, time2 = 0LL;
    struct timespec tt1, tt2;
    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (unsigned int i = 1; i <= TEST_RANGE; i++) {
        char s[MSG_LEN + 1];
        int div3 = i % 3;
        int div5 = i % 5;
        if (!div3) sprintf(s, "Fizz");
        if (!div5) sprintf(s, "Buzz");
        if (!div3 && !div5) sprintf(s, "FizzBuzz");
        if (div3 && div5) sprintf(s, "%u", i);
        sprintf(s, "%s\n", s);
        // printf("%s", s);
    }
    clock_gettime(CLOCK_MONOTONIC, &tt2);
    time1 += (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

    clock_gettime(CLOCK_MONOTONIC, &tt1);
    for (unsigned int i = 1; i <= TEST_RANGE; 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) >> (div3 << 2)], length);
        fmt[length] = '\0';

        sprintf(fmt, "%s\n", fmt);
        // printf(fmt, i);
    }
    clock_gettime(CLOCK_MONOTONIC, &tt2);
    time2 += (long long) (tt2.tv_sec * 1e9 + tt2.tv_nsec) -
                (long long) (tt1.tv_sec * 1e9 + tt1.tv_nsec);

    printf("%lld %lld\n", time1, time2);
    return 0;
}

##### `getTime.sh`

#!/bin/bash
for i in {1..100}
do
  ./cmp_fizzBuzz >> time.txt;
done

實驗結果如下，可以看出 bitwise 的方法確實是比 naive 版本快，詳細的程式可以參考 [Github](https://github.com/Holychung/2020q3_System_Software/tree/main/quiz4)。


:::info
TODO
- 分析 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
### 題目
考慮到整數 `PAGE_QUEUES` 可能有以下數值:
- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) × ($2^n$), n from 1 to 14

給定 `size_t offset`，試著將原本運算:

#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;

由於 PAGE_QUEUES 的數值分佈已知，在整數除法時，可思考加速運算的機制。需要注意，某些硬體平台缺乏整數除法指令 (如 Arm Cortex-A8)，即使 Intel 公司出品的 Core 處裡器 Sandy Bridge 微架構中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)

#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; 效果的程式碼。

### 作答
這邊我們已知除數 `PAGE_QUEUES` 的範圍是 $k\times2^n$，k 的範圍是 1~7，n 是 1~14，然後要對其整數除法進行加速，可以透過對除數跟被除數先進行約分的動作，就是先把 $2^n$ 用 shift 方式處理掉。

看到程式當中的 `__builtin_ffs` 可以參考 [Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)，所以這邊的 `ffs32(x)` 就是代表最低位有多少個 0，也就可以知道我們要往右 shift 幾位。
> Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

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

第 5 6 行就是對被除數 `offset` 跟除數 `divident` 先進行 shift，最後再透過 switch case 進行剩下的除法。不過因為已知除數 `PAGE_QUEUES` 的範圍是 $k\times2^n$，所以把 $2^n$ 除掉後只剩下 $k$，可能的 k 有 3、5、7，因此 cases 需要包含這三個數字。

### 延伸問題
:::info
TODO
練習 LeetCode [51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;
:::