# 2020q3 Homework4 (quiz4)

contributed by < `blueskyson` >

###### tags: `linux2020`

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

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


上圖 [hypercube](https://en.wikipedia.org/wiki/Hypercube) (中文翻譯：超方形) 中，紅色路徑的 `0100` 到 `1001` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為 `3`，而藍色路徑的 `0110` 到 `1110` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 則是 `1`。

運用[第 3 周測驗](https://hackmd.io/@sysprog/2020-quiz3)提到的 `__builtin_popcount` (gcc extension 之一)，我們可實作如下:

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

請補完程式碼。

### 解題

所求 hamming distance 是每個位元的差， xor 正好可以將數值不一樣的位元設為 1 ，數值相同的位元設為 0 ，再利用 `__builtin_popcount` 算不一樣的位元的個數，即可求出 hamming distance 。所以==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 個節點


Input:

 ["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]

:::info
上方為 JSON 格式，其中:
- 7 表示共有 7 個節點
- `GetKthAncestor(3, 1)` 預期回傳 `1`，後者是 `3` 的父節點，即「上 1 代」;
- `GetKthAncestor(5, 2)` 預期回傳 `0`，後者是 `5` 的祖父節點，即「上 2 代」;
- `GetKthAncestor(6, 3)` 預期回傳 `-1`，因為不存在這樣的節點
:::

Output:

[null,1,0,-1]

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

請補完。

### 解題

由上面 10 到 17 行程式碼可以看出 `parent` 是 `int*` 的陣列，對於每個 `int*` 再配置 `int` 陣列，把每個元素初始化為 -1 。所以 `parent` 為 `int` 指標的指標，==AAA== = `**parent` 。

接下來，第 19 及 20 行初始化上一代父節點 ， `obj->parent[i][0]` 的值即為第 `i` 個節點的上一代父節點。

第 22 到第 31 行持續更新第 `i` 個節點的上 `j` 代父節點，直到更新至根 (即 `parent[i][j] == -1`) 。在第 25 行，確認 `parent[i][j - 1]` 是否已經為根:

- 是，將 `parent[i][j]` 也設為 -1 ;
- 否，將 `parent[i][j]` 設為 `parent[i][j - 1]` 的上一代父節點

所以 ==BBB== = -1 ，用來求得 `parent[i][j - 1]` 的值。

參考 [RusselCK](https://hackmd.io/@RusselCK/sysprog2020_quiz4) 同學的解法:

>k = 7 = $(0000 0111)_2$
7th = ( 1th 的 2th ) 的 4th

所以 ==CCC== = `1 << i`

## 測驗 `3`

:::info
>白板 coding 其實本意 (最好不要是) 不是考一些你已經會的東西，而是考一個你可能不會的問題，然後你要 keep trying, keep doing 下去，因為它的本質是在考一個未來你可能碰到的問題 (而且可能 Google 不到)。
出處: [簡單的 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”
- 如果都不是，就印出數字本身

直覺的實作程式碼如下: (`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;
}

觀察 `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 程式碼: (`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;
}

gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。

請補完。

### 解題

- 當 `i` 為 3 的倍數時，將 `"FizzBuzz%u"` 的第 0 至第 3 個位置，也就是 `"Fizz"` 複製到 `fmt`
- 當 `i` 為 5 的倍數時，將 `"FizzBuzz%u"` 的第 4 至第 7 個位置，也就是 `"Buzz"` 複製到 `fmt`
- 當 `i` 為 15 的倍數時，將 `"FizzBuzz%u"` 的第 0 至第 7 個位置，也就是 `"FizzBuzz"` 複製到 `fmt`
- 其餘狀況，將 `"FizzBuzz%u"` 的第 8 至第 9 個位置，也就是 `"%u"` 複製到 `fmt`

當 ==KK1== = `div5`, ==KK2== = `div3`, ==KK3== = `2` 即可達成上述要求

## 測驗 `4`

考慮到整數 `PAGE_QUEUES` 可能有以下數值:

- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) × (2ⁿ), 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](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html):
>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.
- [Integer division is slow](https://kristerw.blogspot.com/2017/05/integer-division-is-slow.html)

### 解題

上面程式碼第 5, 6 行用於排除除術與被除數的 2ⁿ 公因數，接下來 7 到 9 行只須考慮 1 到 8 中不包含 2ⁿ 的數字，即 `3`, `5`, `7` 。 `6` 為 3 * 2 ，可用 __builtin_ffs() 及 /=3 完成。