# 2020q3 Homework4 (quiz4) contributed by < `dalaoqi` > ## 測驗一 此題需要完成可以實作出兩整數的 Hamming distance。 ```cpp int hammingDistance(int x, int y) { return __builtin_popcount(x OP y); } ``` 只要找出相異的位元並將之並訂為 1 ，再利用 `__builtin_popcount` 就可以算出兩數的 Hamming distance。 因此 `OP` 為 `^`。 ## 測驗二 此題為 LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 首先要先補完樹狀結構元素 struct ```cpp typedef struct { AAA; int max_level; } TreeAncestor; ``` `AAA` 的答案可以從 `treeAncestorCreate`的 ```cpp TreeAncestor *obj = malloc(sizeof(TreeAncestor)); obj->parent = malloc(n * sizeof(int *)); ``` 推敲出。其中有兩次的 `malloc` 分別是分配整個 `TreeAncestor *` 及 `TreeAncestor` 內的 `parent`。 在 `parent` 部分分配了 `n * sizeof(int *)` ，因此可以推測 `AAA` 就是 `int **parent`。 以下函式需要修改 `BBB` 使該函式能夠順利運作。 ```cpp 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; } ``` * `max_level` * 在有 n 個節點的最差的情況下，會有 n-1 個祖先 * 如果想要將全部的節點都存下來需要 n * (n - 1) * sizeof(int) 空間，空間成本太大 * 這裡使用折衷的方式，只存每個 level 的第一格節點，即第1、2、4、8、...$2^n$ 節點 ``` obj->parent[i][j] = obj->parent[i][j + BBB] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1]; ``` 這行的目的會去確認每個節點的第 j 祖先，所以一開始會去確認是否有第 j-1 個祖先，所以這裡的 `BBB` 為 -1。 以下函式需要修改 `CCC` 使該函式能夠順利運作。 ```cpp 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; } ``` 目的是要去找到 node 的第 k 個祖先。 假設 `k = 7`，就是去找到 node 的第四個祖先的第二個祖先的第一個祖先。 所以 `CCC` 為 `1 << i`。 ## 測驗三 此題需要利用 bitwise 實作的 FizzBuzz `is_divisible` 可參考 [2020q3 Homework2 (quiz2)](https://hackmd.io/@dalaoqi/2020q3-quiz2#%E6%B8%AC%E9%A9%97%E5%9B%9B) ```cpp #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; } ``` 首先，考慮輸入的數字是三的倍數非五的倍數，即 div3 = 1, div5 = 0，輸出字串為 `Fuzz`， `length = 4`。 考慮輸入的數字是五的倍數非三的倍數，即 div3 = 0, div5 = 1，輸出字串為 `Buzz`， `length = 4`。 考慮輸入的數字同時是三的倍數也是五的倍數，即 div3 = 1, div5 = 1，輸出字串為 `FuzzBuzz`， `length = 8`。 其餘狀態，即 div3 = 1, div5 = 1，輸出字串為 ` `， `length = 2`。 觀察字串，要從哪個地方開始複製 * 如果輸入的數字是三的倍數非五的倍數或同時是三的倍數也是五的倍數，需要從字串位置 `0` 的位置開始複製 * 輸入的數字是五的倍數非三的倍數需要從字串位置 `4` 的位置開始複製 * 其餘狀態需要從字串位置 `8` 的位置開始複製 根據上述這些推論，可以推得 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 為 `(MSG_LEN >> div5) >> (div3 << 2)`。 ## 測驗四 此題需要利用 ` __builtin_ffs` 把可以用位移取代的除法先行計算，減少整數除法的開銷 ```cpp #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 } ``` 從 `PAGE_QUEUES` 我們可以知道數值的範圍為 $k \times 2^n$，$1 \leq n \leq 8$, $1 \leq n \leq 14$ 一開始有定義一個巨集 `ffs32(x)`，主要會回傳 $log_2(x)$，而 `blockidx` 以及 `divident` 會去先進行位移 $log_2(x)$ 簡化，消除 2 的倍數 ， 因此在 switch 只要去針對非 2 的倍數的 k 額外計算即可，除了 1 的情況不用額外處理外，其餘的 3、5、7 就是本題的答案。