# [2020q3](http://wiki.csie.ncku.edu.tw/sysprog/schedule) 第 4 週測驗題
###### tags: `sysprog2020`
:::info
目的: 檢驗學員對 [C 語言指標](https://hackmd.io/@sysprog/c-pointer), [數值系統](https://hackmd.io/@sysprog/c-numerics) 及 [bitwise 操作](https://hackmd.io/@sysprog/c-bitwise) 的認知
:::
==[作答表單](https://docs.google.com/forms/d/e/1FAIpQLSeeCzlevUyMjcUSpkdh3sVp9Zwqg-MSUHv0JU0yt5XLgKBr9Q/viewform)==
### 測驗 `1`
LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/) 提及，兩個整數間的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance)，例如整數 `1` 的二進位為 `0 0 0 1`，而整數 `4` 的二進位為 `0 1 0 0`，則 `1` 與 `4` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為 `2`。
```
1 (0 0 0 1)
4 (0 1 0 0)
[ ] [ ]
| |
\_ 2 _/
```
上圖 [hypercube](https://en.wikipedia.org/wiki/Hypercube) (中文翻譯：超方形) 中，紅色路徑的 `0100` 到 `1001` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 為 `3`，而藍色路徑的 `0110` 到 `1110` 的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_distance) 則是 `1`。
運用[第 3 周測驗](https://hackmd.io/@sysprog/2020-quiz3) 提到的 `__builtin_popcount` (gcc extension 之一)，我們可實作如下:
```cpp
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
請補完程式碼。
參考資訊:
* [詳解二進位數中 `1` 的個數](http://github.tiankonguse.com/blog/2014/11/16/bit-count-more.html)
==作答區==
OP = ?
* `(a)` `|`
* `(b)` `&`
* `(c)` `^`
* `(d)` `+`
* `(e)` `-`
:::success
延伸問題:
1. 解釋上述程式碼運作原理，並舉出不使用 gcc extension 的 C99 實作程式碼;
2. 練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交 (submit) 你的實作 (C 語言實作)，並確保執行結果正確且不超時
3. 研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](http://bit.ly/abstract-algebra)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說;
- 搭配閱讀 [Hamming codes, Part I](https://youtu.be/X8jsijhllIA) 及 [Hamming codes, Part II](https://youtu.be/b3NxrZOu_CE)，你可適度摘錄影片中的素材，但應當清楚標註來源
4. 研讀 [Reed–Solomon error correction](https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction)，再閱讀 Linux 核心原始程式碼的 [lib/reed_solomon 目錄](https://github.com/torvalds/linux/tree/master/lib/reed_solomon)，抽離後者程式碼為單獨可執行的程式，作為 ECC 的示範。
:::
---
### 測驗 `2`
LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 大意:
> 給你一棵樹，樹上有 n 個節點，編號自 0 到 $n - 1$。樹以父節點陣列的形式提供，其中 `parent[i]` 是節點 i 的父節點。樹的根節點是編號為 0 的節點。請設計 `treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)` 函式，回傳節點 node 的第 k 個祖先節點。若不存在這樣的祖先節點，回傳 `-1`。樹節點的第 k 個祖先節點是從該節點到根節點路徑上的第 k 個節點
Input:
```json
["TreeAncestor","getKthAncestor","getKthAncestor","getKthAncestor"]
[[7,[-1,0,0,1,1,2,2]],[3,1],[5,2],[6,3]]
```
:::info
:information_source: 上方為 [JSON](https://www.json.org/json-en.html) 格式，其中:
* `7` 表示共有 7 個節點
* `GetKthAncestor(3, 1)` 預期回傳 `1`，後者是 `3` 的父節點，即「上 `1` 代」;
* `GetKthAncestor(5, 2)` 預期回傳 `0`，後者是 `5` 的祖父節點，即「上 `2` 代」;
* `GetKthAncestor(6, 3)` 預期回傳 `-1`，因為不存在這樣的節點
:::
Output:
```json
[null,1,0,-1]
```
以下是參考 C 程式實作:
```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 = ?
* `(a)` `int ***parent`
* `(b)` `int **parent`
* `(c)` `int *parent`
BBB = ?
* `(a)` `(-2)`
* `(b)` `(-1)`
* `(c)` `0`
* `(d)` `1`
* `(e)` `2`
CCC = ?
* `(a)` `1`
* `(b)` `i`
* `(c)` `i >> 1`
* `(d)` `i >> k`
* `(e)` `k << i`
* `(f)` `1 << i`
:::success
延伸問題:
1. 解釋上述程式碼運作原理，指出可改進的地方，並實作對應的程式碼;
2. 在 `treeAncestorCreate` 函式內部，若干記憶體被浪費，請撰寫完整測試程式碼，並透過工具分析;
3. 在 LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者;
:::
---
### 測驗 `3`
:::info
> 白板 coding 其實本意 (最好不要是) 不是考一些你已經會的東西，而是考一個你可能不會的問題，然後你要 keep trying, keep doing 下去，因為它的本質是在考一個未來你可能碰到的問題 (而且可能 Google 不到)。
出處: [簡單的 FizzBuzz 藏有深度 (Google 面試題)](https://medium.com/@Bear_/%E7%B0%A1%E5%96%AE%E7%9A%84-fizzbuzz-%E8%97%8F%E6%9C%89-%E6%B7%B1%E5%BA%A6-google-%E9%9D%A2%E8%A9%A6%E9%A1%8C-f5e66e3a97be)
:::
考慮貌似簡單卻蘊含實作深度的 [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz) 題目:
* 從 1 數到 n，如果是 3的倍數，印出 "Fizz"
* 如果是 5 的倍數，印出 "Buzz"
* 如果是 15 的倍數，印出 "FizzBuzz"
* 如果都不是，就印出數字本身
直覺的實作程式碼如下: (`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;
}
```
觀察 `printf` 的(格式)字串，可分類為以下三種:
1. 整數格式字串 `"%d"` : 長度為 2 B
2. "Fizz" 或 "Buzz" : 長度為 4 B
3. "FizzBuzz" : 長度為 8 B
考慮下方程式碼:
```cpp
#define MSG_LEN 8
char fmt[MSG_LEN + 1];
strncpy(fmt, &"FizzBuzz%u"[start], length);
fmt[length] = '\0';
printf(fmt, i);
printf("\n");
```
我們若能精準從給定輸入 `i` 的規律去控制 `start` 及 `length`，即可符合 FizzBuzz 題意:
```cpp
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
```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;
}
```
gcc-9 還內建了 [FizzBuzz optimization](https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853) (Bug 82853 - Optimize x % 3 == 0 without modulo)。
請補完。
==作答區==
KK1 = ?
* `(a)` div5
* `(b)` div3
* `(c)` 2
* `(d)` 1
KK2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 2
* `(d)` div3
* `(e)` div5
KK3 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 2
* `(d)` div3
* `(e)` div5
:::success
延伸問題:
1. 解釋上述程式運作原理並評估 `naive.c` 和 `bitwise.c` 效能落差
* 避免 stream I/O 帶來的影響，可將 `printf` 更換為 `sprintf`
2. 分析 [Faster remainders when the divisor is a constant: beating compilers and libdivide](https://lemire.me/blog/2019/02/08/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](https://github.com/lemire/fastmod)
:::
---
### 測驗 `4`
考慮到整數 `PAGE_QUEUES` 可能有以下數值:
* (1 or 2 or 3 or 4)
* (5 or 6 or 7 or 8) $\times$ (2^n^), n from 1 to 14
給定 `size_t offset`，試著將原本運算:
```cpp
#include <stdint.h>
size_t blockidx = offset / PAGE_QUEUES;
```
由於 `PAGE_QUEUES` 的數值分佈已知，在整數除法時，可思考加速運算的機制。需要注意，某些硬體平台缺乏整數除法指令 (如 Arm Cortex-A8)，即使 Intel 公司出品的 Core 處裡器 [Sandy Bridge 微架構](https://en.wikipedia.org/wiki/Sandy_Bridge)中，針對 64 位元整數的除法運算，會佔用 40 到 103 個處理器週期，運算成本仍屬沈重。
> 來源: [Agner Fog’s instruction tables](https://www.agner.org/optimize/instruction_tables.pdf)，第 180 頁
於是我們可預先進行計算，從而避免整數除法指令的使用: (假設在 x86_64 硬體執行 GNU/Linux 並透過 gcc/clang 編譯)
```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
}
```
其中 `CASES` 可能形如:
```cpp
case 2: blockidx /= 2;
break;
```
這樣的組合，請用最少的 case-break 敘述做出同等 `size_t blockidx = offset / PAGE_QUEUES;` 效果的程式碼。
參考資料:
* 摘自 [Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html):
> Built-in Function: `int __builtin_ffs (int x)`
> Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero.
* [Integer division is slow](https://kristerw.blogspot.com/2017/05/integer-division-is-slow.html)
==作答區==
`CASES` 至少該包含哪些數字: (複選)
* `(a)` 2
* `(b)` 3
* `(c)` 4
* `(d)` 5
* `(e)` 6
* `(f)` 7
* `(g)` 8
* `(i)` 9
* `(j)` 10
:::success
延伸問題:
1. 解釋程式運算原理，可搭配 Microsoft Research 的專案 [snmalloc](https://github.com/microsoft/snmalloc) 來解說;
* 對應的原始程式碼 [src/mem/sizeclass.h](https://github.com/microsoft/snmalloc/blob/master/src/mem/sizeclass.h#L54-L145)
2. 練習 LeetCode [51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 `__builtin_ffs`，大幅降低記憶體開銷;
:::
---
Sign in with Wallet
Connect another wallet