# 2020q3 Homework4 (quiz4)
contributed by < `OscarShiang` >
## 作業要求
- [x] 重新回答第 4 週測驗題
## 測驗 `1`
本題的用意在於實作出可以計算兩個給定數字之間的 Hamming distance
根據 [Hamming distance - Wikipedia](https://en.wikipedia.org/wiki/Hamming_distance) 中的定義
> The Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different.
假設給定的兩個字串 `001` 與 `010` ，因為兩者有在對應位置上有兩處不同，因此 Hamming distance 是 2。
而看到本題實作的部分
```cpp
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
因為使用 `__builtin_popcount` 來計算 Hamming distance ，所以我們只需要將相異的兩個位元設定為 `1` 即可，所以 `OP` 的答案就會是
> OP = `^`
## 測驗 `2`
本題嘗試實作一個樹狀結構以及相關的操作，包括
- `treeAncestorCreate`
- `treeAncestorGetKthAncestor`
- `treeAncestorFree`
並且以下圖作為範例來實作
```graphviz
digraph {
node [shape=circle]
0 -> {1, 2} [arrowhead=none]
1 -> {3, 4} [arrowhead=none]
2 -> {5, 6} [arrowhead=none]
}
```
### AAA
本題的部分是要補完樹狀結構元素的 `struct`，根據
```cpp
typedef struct {
AAA;
int max_level;
} TreeAncestor;
```
的部分我們可以知道這個元素的結構包括一個 int 變數 `max_level` 用記錄從這個節點向上還有多少層元素。
接著我們可以看到 `treeAncestorCreate` 函式中關於節點初始化的部分
```cpp
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
```
從這邊我們可以看到 `TreeAncestor *` 這個變數 `obj` 的結構中有 `parent` 這個 field，並從 `malloc` 的參數得知，我們取得了一段可以存取 `n` 個 `int *` 型態的變數的空間，所以根據上述的線索我們可以推測在 AAA 中缺少的 field 應該是
> AAA = `int **parent`
### BBB
根據 BBB 所在位置的程式碼
```cpp
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][BBB] == -1
? -1
: obj->parent[obj->parent[i][j - 1]][j - 1];
if (obj->parent[i][j] != -1)
quit = 0;
}
if (quit)
break;
}
```
我們可以從三元運算子 else 的條件看到，如果 `obj->parent[i][BBB] == -1` 的條件不成立時，則會將 `obj->parent[obj->parent[i][j - 1]][j - 1]` 的數值賦值到 `obj->parent[i][j]` 中。
因此我們可以判斷 BBB 的部分是在確認是否存在 `obj->parent[i][BBB]` 亦即該變數的數值不等於 `-1`，才能做 `obj->parent[obj->parent[i][j - 1]][j - 1]` 取值的運算。
因為根據 ISO/IEC 9899 6.5.2.1 Array subscripting 的描述
> The definition of the subscript operator [] is that **E1[E2]** is identical to **(*((E1)+(E2)))**.
若我們嘗試取得一個 array 編號 -1 的元素時，根據上述的概念，我們實際上會存取到在 array 第 0 個元素之前的資料，除了程式將無法按照我們預期的執行之外，也會造成記憶體存取上的疑慮，因為我們正在對程式宣告的記憶體空間以外的其他位址進行操作。
因此為了避免這樣的問題，我們才需要事先確認 `obj->parent[i][BBB] == -1` 的情況是否發生
所以 BBB 的答案就會是
> BBB = `(-1)`
### CCC
為了了解這題的實作觀點，我們首先可以看到 `treeAncestorCreate` 函式中針對 `max_level` 的計算
```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 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 max_level = 32 - __builtin_clz(n) + 1` 這個部分本質上就是在做 $log_2 \ n + 1$ 的動作，也就是在計算這個二元樹的最多會有多大的 level。
在本題中，因為共有 7 個節點，所以最多會有 3 個 level (第 0 ~ 2 層)，而最後 `+1` 的部分是為了保留終止的數值 `-1`。
因此我們可以知道本題的結構在 `obj->parent` 中保存的狀態應該如下表所示
```
[0]: -1 -1 -1 -1
[1]: 0 -1 -1 -1
[2]: 0 -1 -1 -1
[3]: 1 0 -1 -1
[4]: 1 0 -1 -1
[5]: 2 0 -1 -1
[6]: 2 0 -1 -1
```
而接著在 `treeAncestorGetKthAncestor` 中，也就是 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;
}
```
這邊所採取的方式是將給定的 `k` 利用 `i` 拆成二的次方的級數
例如我們給定
$$
k = 7
$$
則透過 for 迴圈，我們應該要將其拆成
$$
\begin{align}
k &= 1 + 2 + 4 \\\\
&= 2^0 + 2^1 + 2^2
\end{align}
$$
接著將這些數字分別帶入 `obj->parent` 的陣列中找尋對應的節點
所以根據上述的條件，CCC 應該為
> CCC = `1 << i`
### 修改實作
從 `CCC` 中我們可以發現在尋找第 k 個祖先節點的時候我們是透過 2 的冪次逐漸求得我們所要的答案，但是因為這些資訊在 `obj->parent` 中全部都有記錄，所以我們也可以利用下列的方式來取得答案
```cpp
int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)
{
int max_level = obj->max_level;
if (k > max_level)
k = max_level;
node = obj->parent[node][k - 1];
return node;
}
```
再來因為我們剛剛在解釋 `BBB` 的時候，有提到每個節點的最後面都有一個 `-1` 的數值作為終止的標記。
但是在 `treeAncestorCreate` 在最後有這麼一行操作
```cpp
obj->max_level = max_level - 1;
```
而在 `treeAncestorGetKthAncestor` 函式中是如此操作這個陣列
```cpp
for (int i = 0; i < max_level && node != -1; ++i)
if (k & (CCC))
node = obj->parent[node][i];
```
從這邊我們就可以看到在這些操作中，我們顯然根本不會使用到在 `treeAncestorCreate` 的時候考慮到的最後一個終止的數值。因為我們在設定完最後一個位置之後，有將邊界做調整，對應到 for 迴圈的邊界，所以在正常使用 `max_level` 作為邊界來操作的時候，我們是不會用到陣列的最後一個 `-1` 的。
因此我們可以再針對這個實作做以下的調整
```diff
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
/* Initialize the variables */
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
- int max_level = 32 - __builtin_clz(n) + 1;
+ int max_level = 32 - __builtin_clz(n);
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];
/* Construct the relations of each parents */
for (int j = 1;; j++) {
int quit = 1;
for (int i = 0; i < parentSize; i++) {
obj->parent[i][j] = obj->parent[i][j - 1] == -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;
+ obj->max_level = max_level;
return obj;
}
```
## 測驗 `3`
本題嘗試使用 bitwise 的方式實作一個滿足以下條件的 Fizzbuzz 題目
- 從 1 數到 n，如果是 3 的倍數，印出 "Fizz"
- 如果是 5 的倍數，印出 "Buzz"
- 如果是 15 的倍數，印出 "FizzBuzz"
- 如果都不是，就印出數字本身
透過給定數值的規律來控制輸出字串的形式
```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;
}
```
:::info
:bulb: 關於 `is_divisable` 的解釋可以參考 [2020q3 Homework2 (quiz2)](/pzCs1jd9TQGtTcjG-_eWzg)
:::
所以根據 `is_divisable` 函式的定義，`div3` 與 `div5` 只有 `0` 或 `1` 兩種結果，因此我們只要專注在如何用 `div3` 與 `div5` 湊出對應的字串即可。
因此我們可以考慮以下的情況
考慮給定的數字是 3 的倍數，亦即 `div3 = 1` 且 `div5 = 0`
因為我們要輸出的字串是 `Fuzz`，所以需要先透過 `(MSG_LEN >> KK1) >> (KK2 << KK3)` 計算出 `0`
假設 `KK1` 的答案是 `div3` 而 `KK2` 的答案是 `div5`，則表示 `(8 >> 1) >> (0 << KK3)` 得到 `4`
考慮到 8 這個數字至少要位移 4 次後才會是 0 ，所以可以組合出最大的可能就會是
> KK1 = `div5`
> [color=purple]
> KK2 = `div3` (或 `2`)
> [color=purple]
> KK3 = `2` (或 `div3`)
> [color=purple]
我們可以帶入 `div3 = 0` 且 `div5 = 1` 也就是給定數字是 5 的倍數的情況來驗算
考慮給定 `div3 = 0` 與 `div5 = 1` 的 `(MSG_LEN >> div5) >> (div3 << 2)` 與 `(MSG_LEN >> div5) >> (2 << div3)` 兩種情況
代入數字後兩式就會變成 `(8 >> 1) >> (0 << 2) = 4` 與 `(8 >> 1) >> (2 << 0) = 1`
所以根據計算的結果我們就可以知道正確的組合是
> KK1 = `div5`
> KK2 = `div3`
> KK3 = `2`
### `naive.c` 實作的問題
根據題目給定的 `naive.c` 版本的實作
```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;
}
```
在給定數字 `i` 是 3 或是 5 的倍數的時候可以正常印出規定的字串形式，但是因為上述程式碼在邏輯上採用的是個別判斷是否為 3 或 5 的倍數的手法，所以在遇到 `i = 15 * n (n >= 1)` 的情況的時候會輸出以下的字串
```
i = 1, 1
i = 2, 2
i = 3, Fizz
i = 4, 4
i = 5, Buzz
i = 6, Fizz
i = 7, 7
i = 8, 8
i = 9, Fizz
i = 10, Buzz
i = 11, 11
i = 12, Fizz
i = 13, 13
i = 14, 14
i = 15, FizzBuzzFizzBuzz
i = 16, 16
```
從上列的輸出可以看到在判斷的邏輯上，若 `i` 是 15 的倍數也就表示其是 3 與 5 的倍數，所以在這個實作中，我們不需要額外針對 `i` 是 15 的倍數的情況在處理，因為我們在判斷其為 3 的倍數的時候就會輸出 `Fuzz`；判斷其為 5 的倍數的時候就會輸出 `Buzz` 了
所以我們可以將 `naive.c` 的實作進行修改
```diff
#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;
}
```
省去多餘的邏輯判斷。
## 測驗 `4`
本題的用意在於使用 `__builtin_ffs` 來減少整數除法的開銷
考慮到 `PAGE_QUEUES` 的數值範圍如下
- (1 or 2 or 3 or 4)
- (5 or 6 or 7 or 8) × (2^n^), n from 1 to 14
用以進行以下的運算
```cpp
#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;
```
因為 `PAGE_QUEUES` 的數值最大可能是 $8 \times 2^{14}$ 所以若不進行化簡而直接做整數除法的話會運算的成本，因此我們可以使用 `__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` 的範圍已知，所以如果經過 `ffs` 的化簡後則可能的除數剩下
$$
1,\ 3,\ 5,\ 7
$$
四種可能，除去被除數為 1 的情況，`CASES` 至少要包括
> (b) 3
> (d) 5
> (f) 7
三個情況才行。
## 參考資料
- [2020q3 第 4 週測驗題](https://hackmd.io/@sysprog/2020-quiz4)
- [Hamming distance - Wikipedia](https://en.wikipedia.org/wiki/Hamming_distance)
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet