# 2020q3 Homework4 (quiz4)
contributed by < `Sisker1111` >
###### tags: `進階電腦系統理論與實作`
> [測驗題](https://hackmd.io/@sysprog/2020-quiz4)
>
## 測驗 1
LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為 2。
運用第 3 周測驗 提到的 __builtin_popcount (gcc extension 之一)，我們可實作如下:

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

Hamming Distance 是要找出兩個二進位數字不同的 bits 有幾個，已知`__builtin_popcount`會 return `bit = 1`的數量，也就是說，若兩數某一 bit 不同，我們要 reset 為 1，否則就 reset 為 0，很明顯的，`OP = ^`.

## 測驗 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 個節點

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

`treeAncestorCreate`
* 對於 n 個節點，最差情形下是有 n - 1 代的祖先，可以想到如果把每個節點從第 0 個到第 n - 1 個祖先都紀錄下來，就可以在 treeAncestorGetKthAncestor 時有 O(1) 的時間效率
* 然而這需要建立 sizeof(int) * (n * n - 1) 的空間，當 n 越大時越不可行，如果不預先建立查詢的表，每一次 treeAncestorGetKthAncestor 就變成要承受時間成本.
* 因此，一個時間和空間的 trade-off，就是僅記錄每個點的第 1、2、4、…2^n 個祖先是誰

回到程式碼:
1. 從 11~15 行可知，`obj->parent`是一個二維陣列，因此 struct裡的`AAA`應要是一個可以動態 malloc 二維空間的變數，故選`(b)` `int **parent`
2. 接著看 19~34 行，已知`parent[i]`是節點 i 的父節點，樹的根節點是編號為 0 的節點，可以大致判斷出`obj->parent[i][0]`是存放節點 i 的父節點，`obj->parent[i][1]`是存放節點 i 父節點的父節點......以此類推.
* 第 25 行在判斷說，如果 i 不存在父節點，則節點 i 父節點的父節點也不存在，因此`BBB = -1`.
* 如果存在的話，舉例來說，a 的第 $2^j$ 個 祖先就是第 $2^{j-1}$ 個祖先的第 $2^{j-1}$ 個祖先($2^{j-1}$+$2^{j-1}$ = $2^j$).
3. Code 36~43 行是要找出節點 node 的第 k 的祖先，k 可以拆成 $2^j$ 的組合，例如第 6 個祖先可以拆成是搜尋第 4 個祖先的第 2 個祖先，因此答案為`(f)` `1 << i`

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

* Runtime : 0 ms, faster than 100.00% of C++ online submissions.
Memory Usage : 6.1 MB, less than 40.99% of ...

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

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

觀察 printf 的(格式)字串，可分類為以下三種:

1. 整數格式字串 "%d" : 長度為 2 B
2. “Fizz” 或 “Buzz” : 長度為 4 B
3. “FizzBuzz” : 長度為 8 B

考慮下方程式碼:

#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");

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

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

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

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

本來想藉由控制"擷取字串的長度"及"字串的起始位置"，來印出不同 case 的結果:
程式碼前半在 [quiz2](https://hackmd.io/@sysprog/2020-quiz2) 已經看過，是用來判斷該數是否能被 3 or 5 來整除，接著看向 Code 第 17 行:
這邊得用 4 個 case 來做刪去法，才比較好判斷答案是那些:
1. 某數 x 不會被 3 整除且不會被 5 整除，為了印出`%d`，那麼應該從該字串的第 8 個位置開始擷取 2B 字串，那麼 KK1 中 ( c )、( d )，KK2 中 ( b )、( c ) 就一定不能是答案.
2. 某數 x 會被 3 整除且不會被 5 整除，為了印出`Fizz`，那麼應該從該字串的第 0 個位置開始擷取 4B 字串，若要把 8 變成 0 必須達成 `>> 4`，KK1 為 ( a )、( b )都有可能，這邊先假設`KK1 = div5`.
3. 某數 x 不會被 3 整除且會被 5 整除，為了印出`Buzz`，那麼應該從該字串的第 4 個位置開始擷取 4B 字串，已知`KK1 = div5`，`(MSG_LEN >> 1) = 4` ，`(KK2 << KK3)`必須為 0，KK2 中的 ( e )不可能是答案.
4. 某數 x 會被 3 整除且會被 5 整除，為了印出`FizzBuzz`，那麼應該從該字串的第 0 個位置開始擷取 8B 字串，已知`(MSG_LEN >> div5) = 4`，KK2 的 (a) 不可能是答案，因此 KK2 只剩 `(d)` `div3`一種可能，要滿足` div3 << KK3`的結果可以使得`(MSG_LEN >> 1) >> (1 << KK3) = 0`，KK3 只有`(e)` `(2)`能滿足且能同時滿足以上 4 種 case.
5. 重回 Step.2 假設 `KK1 = div3`，會發現找不到一組解能同時滿足 4 種 case.

## 4. 測驗 4
考慮到整數 PAGE_QUEUES 可能有以下數值:

* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) x (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 微架構](https://en.wikipedia.org/wiki/Sandy_Bridge)中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。

> 來源: [Agner Fog’s instruction tables](https://www.agner.org/optimize/instruction_tables.pdf)，第 180 頁

於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 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;` 效果的程式碼。

* 摘自 Built-in Functions Provided by GCC:
>Built-in Function: int `__builtin_ffs (int x)`
Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.

觀察 `PAGE_QUEUES`，可以知道其數值都可以表示成 k x $2^n$，其中 k 是介於 1 到 8 之間，n 則介於 0 到 14 之間，回想 [quiz2](https://hackmd.io/@sysprog/2020-quiz2) `測驗 3`，對於 $2^n$ 的除法運算可以轉為 bitwise operator，因此:
* `ffs32(x)`的作用就是找到 $2^n$ 中的 n 是多少.
* `blockidx = offset >> ffs32(divident);`用來將 offset/=$2^n$.
* `divident >>= ffs32(divident);`用來將`PAGE_QUEUES`/=$2^n$.
* 因此 switch case 只要針對前面的 k 去計算即可，需要特別處理的 k 值只需要有 `k=3` `k=5` `k=7`，其餘`k=4` `k=6` `k=8` 都已經被包含在前幾個 case 之中.