# 2020q3 Homework4 (quiz4)
contributed by < `tsengsam` >
[第四週測驗題](https://hackmd.io/@sysprog/2020-quiz4)
---
## 測驗 `1`: Hamming Distance
#### 計算兩數在二進位表示時有幾個位元不同
* 我需要記錄兩數在相對應的位元數值不同的數量：根據題目使用 `popcount` 算 set bit 數量可以推測兩個不同的位元經過 `OP` 計算後應為 `1`，而相對應的運算子便為 `XOR`，本題選 `(c)`。
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
```
---
## 測驗 `2`: LeetCode 1483. Kth Ancestor of a Tree Node
#### 給定一棵 complete binary tree 並從根節點編號 $0$ 自 $n-1$，且已知parent\[i] 是節點 i 的父節點，欲設計能回傳第 k 個祖先節點的函式。
* 樹的資料結構:
```cpp
typedef struct {
AAA;
int max_level;
} TreeAncestor;
```
- 由下面的程式可知 `AAA` 應為儲存指標的指標，故 `AAA` 為 `int **parent`
- 而 `max_level` 記錄著該樹的 level，若只有一個節點 level 為 1
* 原本我以為這題的設計是將每個節點 $i$ 的所有祖先節點 $j$ 都存到 `obj->parent[i][j]`，但當看到 `treeAncestorGetKthAncestor` 函式並不是直接 access `obj->parent[i][j]`，而是以 2 的次方個祖先節點向上尋找，才發現 `obj->parent[i][j]` 存的是第 $2^j$ 個的祖父節點，
* `treeAncestorCreate` 用來建立能記錄 $i$ 節點第 $2^j$ 個祖先節點的樹
```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;
}
```
- Level $l$ 的節點 $x$ 編號滿足 $2^{l-1} \le x \le 2^l - 1$，若將編號用二進制表示可知其 level 由最高的 set bit 決定，因此可透過先前學過的 `__builtin_clz(n)` 來協助計算 set bit 位置。
- Line 7 開始的兩層迴圈在初始化 `obj->parent[i][j]`，表示節點 $i$ 的第 $2^j$ 個祖先節點，若祖先節點不存在值為 `-1`。
- Line 12 是因為接下來使用 Dynamic programming (DP) 技巧故先初始化 `parent[i][0]` 為 $i$ 的第 $2^0$ 個也就是父節點。
- Line 15-24 為用來計算祖先節點的主要迴圈，使用 DP 的技巧從根節點開始逐漸將各節點 $i$ 的祖先節點們記錄到 `parent[i][j]`，Line 18 的三元運算子在計算節點 $i$ 的 第 $2^j$ 個祖先節點，原理是如果 連 $2^{j-1}$ 個祖先不存在的那在更老的祖先 $2^j$ 便不可能存在；若存在則可透過第 $2^{j-1}$ 個祖先的 第 $2^{j-1}$ 個祖先來取得，故 `BBB` 為 `(-1)`。
* `treeAncestorGetKthAncestor` 用來取得第 `k` 個祖先節點的編號
```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;
}
```
之所以 `obj` 能夠只存 2 的次方的祖先節點，是因為任意 `k` 皆能由 2 的次方的數相加組成。譬如 $k = 11 = 2^0 + 2^1 + 2^3$ 時，我可以先找到 i 的第 $2^0$ 個祖先，再從該祖先繼續向上找其第 $2^1$ 個的祖先，最後再找第 $2^3$ 個祖先便能找到第 $k = 11$ 個的祖先了。
`CCC` 確認 `k` 的 set bit，也就是用來確認 2 的多少次方是否為組成 `k` 的數，故為 `1 << i`。
* `treeAncestorFree` 釋放記憶體空間
---
## 測驗 `3`: FizzBuzz
#### 若輸入為 3 個倍數，輸出 "Fizz"；若為 5 的倍數輸出 "Buzz"， 若為 15 倍數則輸出 "FizzBuzz"
* 有別於直觀地用 if 來窮舉所有情況，使用 branchless 的方式來完成
* `is_divisible` 的作法可參考 [quiz2](https://hackmd.io/MxBHGC17QA-h2KXL1KC_nA?view#%E3%80%90%E6%B8%AC%E9%A9%97-4%E3%80%91) 測驗 4
```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;
}
```
* Line 17 第2個參數在判斷當輸入為 3 或 15 的倍數時起始位置為 index 0，若為 5 的倍數時起始位置則在 index 4，因為 `MSG_LEN` 由 8 開始遞減，故先判斷有沒有 Buzz，即 `KK1` 為 `div5`，而若是 3 或 15 倍數時要將 `MSG_LEN` 降至 0 的選項就是 `KK2` 為 `div3`、`KK3` 為 `2` 。
## 測驗 `4`:
#### 將原本含除法 (`/`) 的運算改成能預先處理的程式
* 預先處理的函式為 `__builtin_ffs(x)`，會回傳最低的 1 位元的 index 加 1
* 本提要求的 `divident` 至少包含哪些數字即為 `divident >> ffs32(divident)`，因為已有給定的數值分佈，而任何 2 的次方的數皆會得到 1，其餘則會變成3, 5, 7
###### tags: `linux2020`
Sign in with Wallet
Connect another wallet