# 2020q3 Homework4 (quiz4)
contributed by < `RainbowEye0486` >
## 測驗一
LeetCode 461. Hamming Distance 提及，兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 `0001`，而整數 `4` 的二進位為 `0100`，則 `1` 與 `4` 的 `Hamming distance` 為 `2`。
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
Hamming Distance的原理就是比較兩個 `int` 中間有幾個 bit 不一樣，如果有三個 bit 不一樣就會回傳 3 。分析程式碼，首先 ` return __builtin_popcount` 會回傳 int 參數中的 32 bit 中有幾個 set bit 。後面的 `x OP y` 應該是一個會將兩者不同的位元變成 set bit 的運算，根據真值表的特性，選擇 ^ 運算能將兩者一樣的位元設置 0 ，不一樣的地方設置 1 。
OP = ?
`(a)` |
`(b)` &
**`(c)` ^**
`(d)` +
`(e)` -
## 測驗二
>給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k) 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 -1。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點
此題的作法，是用一個 `table` 去紀錄 `node i` 的第 `j` 個祖先，所以我們會需要一個二維陣列，總共的行數是 `n` ，列數是整個 `tree` 的深度 ，這邊用 `max_level` 代表，所以最深的 `leaf node` 都不會大於整個 `tree` 的深度，所有的節點保證能夠記錄所有的祖先。
```graphviz
digraph tree {
a [label="0"]
b [label="1"]
c [label="2"]
d [label="3"]
e [label="4"]
f [label="5"]
g [label="6"];
a->b;a->c;
b->d;b->e;c->f;c->g;
labelloc="o";
label="tree";
}
```
一開始設定`int max_level = 32 - __builtin_clz(n) + 1` ，以下方例子 `n=7` 為例子，`n` 就是`0x00000007`，`__builtin_clz(n)` 回傳的值是 30 ，所以用32減去會得到2，但是根據圖表，我們至少需要3列才夠，所以需要加一。這是我們直覺的推測，如果以邏輯推算，因為7個節點，至少需要$2^3$個位置才能紀錄，而 `__builtin_clz(n)` 回傳的是 "由左數起第一個碰到 set bit 的位元數" ，所以紀錄的數值必須再加一才會是最小能夠容納得下所有祖先節點的 `table` 列數。
|i\j | $2^0$ | $2^1$ | $2^2$ |
| --- | --- | --- | --- |
|**0**|0|-1|-1|
|**1**|1|0|-1|
|**2**|2|0|-1|
|**3**|3|1|0|
|**4**|4|1|0|
|**5**|5|2|0|
|**6**|6|2|0|
```cpp=
#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);
}
```
選項裡面都是關於 `parent` 指標的不同型態，需要判斷的是它究竟紀錄的是甚麼東西。
```cpp=3
typedef struct {
AAA;
int max_level;
} TreeAncestor;
```
由第 11 和 15 行就可以看出來，這邊做的是一個 $n * max\_level$的二維陣列的概念，所以原本的 `parent` 就會是一個指標的指標。
```cpp=11
obj->parent = malloc(n * sizeof(int *));
```
```cpp=15
obj->parent[i] = malloc(max_level * sizeof(int));
```
AAA = ?
**`(a)` int *** parent**
`(b)` int **parent
`(c)` int *parent
18 行之前，對 table進行初始化的動作，把每個元素先設置為 -1 ，然後分析這個 `parent table` 的意思是什麼。
```cpp=20
obj->parent[i][0] = parent[i];
```
這邊的 `obj->parent[i][0]` 指的是在 `struct` 結構內的 `**parent` ，也就是 `table` 的第一排，而後面的 `parent[i]` 則是傳入參數的 `*parent` ，紀錄的是整個 `tree` 的節點(用父節點形式表示)。根據 20 行，每個節點的第 $2^0$ 代祖先都是自己本身。
```cpp=25
obj->parent[i][j] = obj->parent[i][j + BBB] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
```
我們已經知道所有的 `parent[i]` 在 $j=0$ 的時候祖先是自己，接下來透過對 $j=1、2、3...$ 情形去做檢查，25行這邊，想要找出 `parent[i][j]` 這個節點應該放入誰，因此判斷這個 `i` 元素的第 $2^{j+BBB}$ 個祖先是不是 -1 ，如果是，那 `i` 元素的第 $2^j$ 個祖先也會是 -1 (意思是這一格也必須填 -1 )，如果不是，這格代表需要放它兒子節點 `parent[i][j-1]`的第$2^{j-1}$ 個祖先。也就是說，節點 i 記錄了他的 $2^{j-1}$ 個祖先，但是我們不知道第 $2^j$ 個祖先是誰，所以我們透過訪問第 $2^{j-1}$ 個祖先紀錄的節點可以知道**它的第 $2^{j-1}$ 個祖先剛好就是節點 i 的第 $2^j$ 個祖先**。
因為如果第 $2^{j-1}$ ，也就是我的兒子節點就不存在了(等於-1)，第 $2^j$ 個祖先也不會存在，所以其值也會是 -1 。
BBB = ?
`(a)` (-2)
**`(b)` (-1)**
`(c)` 0
`(d)` 1
`(e)` 2
```cpp=38
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` 的第 $2^k$ 個祖先，首先用迴圈檢查，如果 `node` 回傳-1就不用繼續檢查有沒有祖先，其他情況判斷第 i 個祖先是否存在。**CCC**一定跟 i 有關係，所以去除 (a) ，因為需要跟 $2^k$做比較，因此 i 也會跟2的次方倍成比例。
CCC = ?
`(a)` 1
`(b)` i
`(c)` i >> 1
`(d)` i >> k
`(e)` k << i
**`(f)` 1 << i**
## 測驗三
```cpp=
#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;
}
```
為我們解釋了在 1~100 的這個區間內，如果是3的倍數就會印出 `Fizz` 如果是 5 的倍數就會印出 `Buzz` ，如果是 15 的倍數印出 `FizzBuzz` 。
```cpp=
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
結合以上概念實作
```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;
}
```
這邊我們 `M3` 、 `M5` 以及 `is_divisble` 的實作原理是運用了 quiz2 的 bitwise 除法去找出是否有餘數，如果能夠整除， $n*M$ 就會因為 overflow 的關係變成一個相較 M 小許多的數字，因此回傳 `true`。
```cpp=14
unsigned int length = (2 << div3) << div5;
```
接著， `length` 決定了我們的字串長度:
1. 如果不是 3 和 5 的倍數，會印出數字本身，因此長度為 2 。
2. 如果是 3 的倍數 但是不是 5 的倍數，字串長度會是 ($2 << 1$)，也就是4。
3. 如果是 5 的倍數 但是不是 3 的倍數，字串長度會是 ($2 << 1$)，也就是4。
5. 如果是 3 的倍數也是 5 的倍數，字串長度會是 ($2 << 1)<<1$，也就是8。
再用 `strncpy` 來決定字串起始的位置( offset )，到整個字串的結尾( length ):
```cpp=17
strncpy(fmt, &"FizzBuzz%u"[(8 >> KK1) >> (KK2 << KK3)], length);
```
我們先列出所有可能性:
1. 如果不是 3 和 5 的倍數， `offset` 是 8(因為要抓最後面的 "%u" )
1. 如果是 3 的倍數 但是不是 5 的倍數， `offset` 是 0(因為要印出前面的 `Fizz`)
1. 如果是 5 的倍數 但是不是 3 的倍數， `offset` 是 4(因為要印出後面的 `Buzz`)
1. 如果是 3 的倍數也是 5 的倍數， `offset` 是 0。
分析`&"FizzBuzz%u"[(8 >> KK1) >> (KK2 << KK3)]`，第一點，不需要向右移只有如果不是 3 和 5 的倍數，維持8。所以猜測只有**KK1**和**KK2**是0的時候會讓 8 不會有任何右移， **KK1**和**KK2**是 `div5` 和 `div5` 的機率很高。
第二點，發現 3 的倍數也是 5 的倍數 ，以及 3 的倍數 但是不是 5 的倍數兩種可能得到的 offset 都是 0，意味著總右移 的 bit 數超過 3 ，如果 `(KK2 << KK3)` 右移的 bit 數夠多，就不用管 **KK1** 是否是 1 還是 0，所以這邊 **KK1** 應該要放 `div5`。
KK1 = ?
**`(a)` div5**
`(b)` div3
`(c)` 2
`(d)` 1
剩下的兩個，根據前面發現的第一個假設，**KK2**便會是 `div3` (因為 **KK1**和**KK2**一個是 `div5` 另一個是 `div5`)。
KK2 = ?
`(a)` 0
`(b)` 1
`(c)` 2
**`(d)` div3**
`(e)` div5
最後，為了讓右移的 bit 數夠多，我們 **KK3** 要選擇 2。
檢查一下，如果是 5 的倍數 但是不是 3 的倍數，總位移的 bit 數是 (8>>1)>>(0<<2)，也就是4，得到的答案沒錯。
KK3 = ?
`(a)` 0
`(b)` 1
**`(c)` 2**
`(d)` div3
`(e)` div5
## 測驗四
考慮到整數 `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` ，試著將原本運算:
```cpp=
#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;
```
預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)
預先運算的好處是，因為硬體架構的 `PAGE_QUEUES` 可能的值已經固定，所以速度較慢的除法指令就可以透過某種方式實現快速除法，加速硬體效能
```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
}
```
因為原本的被除數跟除數都是十分大的數字，而且後面都接著很多0(二進制)，右移這個動作一次會移動所有後面全為0的部分。
|除數(dec)|除數(bin)|右移之後的除數|
| --- | --- | --- |
|$1*2^n$|0001 000...|1|
|$2*2^n$|0010 000...|1|
|$3*2^n$|0011 000...|3|
|$4*2^n$|0100 000...|1|
|$5*2^n$|0101 000...|5|
|$6*2^n$|0110 000...|3|
|$7*2^n$|0111 000...|7|
|$8*2^n$|1000 000...|1|
1的部分不用處理，因為除1等於數字本身。剩下的部分，只要處理3、5、7的情形即可。
CASES 至少該包含哪些數字: (複選)
`(a)` 2
**`(b)` 3**
`(c)` 4
**`(d)` 5**
`(e)` 6
**`(f)` 7**
`(g)` 8
`(i)` 9
`(j)` 10
Sign in with Wallet
Connect another wallet