# 2020q3 Homework4 (quiz4)
contributed by `joey3639570`
###### tags: `進階電腦系統理論與實作`
## 測驗 `1`
```cpp=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
### 延伸問題:
>解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼;
hammingDistance 要找出有幾個位元的不同，`__builtin_popcount` 用於找出有幾個位元的 `1` ， 利用`x ^ y` 能找出位元值不同者，以下面例子而言:
```
1 (0 0 0 1)
8 (1 0 0 0)
[ ] [ ]
| |
\_ 2 _/
```
`0001` ^ `1000` = `1001`
`__builtin_popcount(1001)` = **2**
答案: `OP` 為 `^`
#### 不使用 GCC Extension
主要避免使用的部分為 `__builtin_popcount()`
參考: [Bits Twiddling Hacks : Counting bits set, Brian Kernighan's way](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)
```cpp=
int hammingDistance(int x, int y) {
int res, n;
n = x ^ y;
for (res = 0; n; n &= n-1) {
res++;
}
return res;
}
```
利用 `n &= n-1` 清除對 the least significant bit set，此方法有機會比直覺的方法(純迴圈)快，仍有用到分支，仍有改善空間。
>練習 LeetCode 477. Total Hamming Distance，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
### 題目解說:
>Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
### 直覺方法:
```c=
int hammingDistance(int x, int y) {
return __builtin_popcount(x ^ y);
}
int totalHammingDistance(int* nums, int numsSize){
int i = 0;
int j;
int result = 0;
for (i ; i < numsSize; i++) {
for (j = i + 1; j < numsSize; j++) {
result += hammingDistance(nums[i], nums[j]);
}
}
return result;
}
```
果不其然，超時
>研讀錯誤更正碼簡介及抽象代數的實務應用，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
>- 搭配閱讀 Hamming codes, Part I 及 Hamming codes, Part II，你可適度摘錄影片中的素材，但應當清楚標註來源
>研讀 Reed–Solomon error correction，再閱讀 Linux 核心原始程式碼的 lib/reed_solomon 目錄，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
## 測驗 `2`
```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);
}
```
### 延伸問題:
>解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼;
`AAA` 可以 `obj->parent = malloc(n * sizeof(int *));` 推論出來，其對於 `obj->parent` 分配了 n 個 `int *` 的空間，這表示 parent 為這些指標們的指標，故 `AAA` 為 `int **parent`
在此可以先了解 `TreeAncestor` 的結構:
- `int **parent` : 可以參考題目解釋，如下
>給你一棵樹，樹上有 n 個節點，編號自 0 到 n−1。樹以父節點陣列的形式提供，其中 parent[i] 是節點 i 的父節點。樹的根節點是編號為 0 的節點。
- `max_level` : 記錄著總共有幾層的樹
`treeAncestorCreate` :
1. 先 malloc 出 `TreeAncestor` 及 `obj->parent` 的記憶體空間
2. 設置 `max_level` 為 `32 - __builtin_clz(n) + 1` ，共 32 位元的狀況下，減掉 leading zero 能得到 Binary Tree 的共有幾層。以 `N` 為 15 (1111) 為例，第一層有 $2^0$ 個， 第二層有 $2^1$ 個，第三層有 $2^2$ 個，第四層有 $2^3$ 個， `32 - __builtin_clz(n) + 1` 為 `32 - 28 + 1` 可以參考下圖 :
```graphviz
digraph G {
a [label="0"]
b [label="1"]
c [label="2"]
d [label="3"]
e [label="4"]
f [label="5"]
g [label="6"];
h [label="7"];
i [label="8"];
j [label="9"];
k [label="10"];
l [label="11"];
m [label="12"];
n [label="13"];
o [label="14"];
a->b;a->c;
b->d;b->e;c->f;c->g;
d->h;d->i;e->j;e->k;
f->l;f->m;g->n;g->o;
labelloc="t";
label="My Graph";
}
```
3. 接下的 for 迴圈，會對於每個 `obj->parent[i]` 分配 `max_level` 個 `int` 的空間，並且初始化這些數值為 -1
4. 下一個 for 迴圈，會對於每個 `obj->parent[i]` 的第 0 個設為 `parent[i]` ，也就是該節點自己本身
5. 再下一個 for 迴圈，利用一 flag `quit` 為迴圈終止條件，藉此建立每個節點的 ancestor 關係
6. 最後 `obj->max_level = max_level - 1`，再把前面多的減一弄回來
:::info
待辦:
- 為何 max_level 一開始 要加 1 ? (``32 - __builtin_clz(n) + 1``)
> 程式碼是寫給你改進的，裡頭故意留下一些缺失，遇到疑慮就大膽假設小心求證
> :notes: jserv
:::
`treeAncestorGetKthAncestor` :
直接探討到 for 迴圈:
- 在 i 未到達 `max_level` 且 node <s>本身有被賦予值</s> 已指定數值，迴圈持續進行，找到正確的階層 (k) ，便會指派 ` obj->parent[node][i]` 給 `node`
:::warning
"assignment" 應依據文意翻譯，若書寫為「賦值」往往會詞語不通順
:notes: jserv
:::
>在 treeAncestorCreate 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;
>在 LeetCode 1483. Kth Ancestor of a Tree Node 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;
## 測驗 `3`
```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;
}
```
### 延伸問題:
>解釋上述程式運作原理並評估 naive.c 和 bitwise.c 效能落差
> - 避免 stream I/O 帶來的影響，可將 printf 更換為 sprintf
- `is_divisible` 及 `M3` 及 `M5` 這部分可以回歸到 quiz2 的測驗 `4` 參考
- `length` 是要 print 出的字串長度，共有以下這幾個可能 :
- `FizzBuzz` : 8
- `Fizz` 及 `Buzz` : 4
- print 數字的狀況下， `length` 會被設為 2，這是整數格式字串 `"%d"` 的長度
- `fmt[MSG_LEN + 1]` 要注意字串有 `'\0'` ，所以要 +1
- 以四種字串可能探討 `strncpy(fmt, &"FizzBuzz%u"[(MSG_LEN >> KK1) >> (KK2 << KK3)], length);`
- 先以下方表格整理字串狀況及對應的變數 :
| 字串 | 開始 Index | div3 | div5 |
|:---------- |:----------:|:----:|:----:|
| `FizzBuzz` | 0 | 1 | 1 |
| `Fizz` | 0 | 1 | 0 |
| `Buzz` | 4 | 0 | 1 |
| 數字 | 8 | 0 | 0 |
綜合上面判斷 `KK1` `KK2` `KK3` :
- `KK1` : 使 Index 有 8 及 4 的可能，倘若只有用到 `KK1` ，字串會是 `Buzz` ，由此推論是 `div5`
- `KK2` 及 `KK3` : 這兩個要一起看，當需要 print 出數字時， Index 要保留為 8 ， 故 `KK2 << KK3` 要為 0 ，綜合 print `Buzz` 和數字的 Case 推出 `KK2` 為 `div3` ， `KK3` 為 `2`
- 最後要把字串的尾端放上 `'\0'`
>評估 `naive.c` 和 `bitwise.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;
}
```
- 首先較顯而易見的是這 `bitwise.c` 大幅減少了分支的使用，這於先前我的[作業 2](https://hackmd.io/@joey3639570/Hkoajm0Vw)有提過減少分支的影響及資安問題
:::info
待辦:
- 效能評估
:::
>分析 Faster remainders when the divisor is a constant: beating compilers and libdivide 一文的想法 (可參照同一篇網誌下方的評論)，並設計另一種 bitmask，如「可被 3 整除則末位設為 1」「可被 5 整除則倒數第二位設定為 1」，然後再改寫 bitwise.c 程式碼，試圖運用更少的指令來實作出 branchless;
參照 fastmod: A header file for fast 32-bit division remainders on 64-bit hardware
## 測驗 `4`
```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
}
```
### 延伸問題:
>解釋程式運算原理，可搭配 Microsoft Research 的專案 snmalloc 來解說;
對應的原始程式碼 src/mem/sizeclass.h
>練習 LeetCode 51. N-Queens，應選擇 C 語言並善用上述的 __builtin_ffs，大幅降低記憶體開銷;
Sign in with Wallet
Connect another wallet