# 2020q3 Homework4 (quiz4)
contributed by < `JimmyLiu0530` >
###### tags: `進階電腦系統理論與實作`
## 測驗1: LeetCode [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)
兩個整數間的 Hamming distance 為其二進位的每個位元的差。請計算輸入參數兩整數 x 與 y 的 Hamming distance，例如整數 1 的二進位為 0 0 0 1，而整數 4 的二進位為 0 1 0 0，則 1 與 4 的 Hamming distance 為 2。
```c=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
### 程式說明
唯有兩數的某一位元相異，他們的 hamming distance 才會加1，因此先對兩數 x, y 作 `^`，再利用 `__builtin_popcount`計算有幾個位元為1，即為 hamming distance，所以`OP = ^`。
### 延伸問題
#### 1. 舉出不使用 gcc extension 的 C99 實作程式碼。
```c=
int hammingDistance_v2(int x, int y) {
int total = 0;
for (int i = 0; i < 31; i++) {
int oneCount = 0;
if (((1 << i) & x) != 0)
oneCount++;
if (((1 << i) & y) != 0)
oneCount++;
total += oneCount * (2 - oneCount);
}
return total;
}
```
仿照延伸問題2的做法，詳細的原理見下方。
#### 2. 練習 LeetCode [477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/)，你應當提交你的實作，並確保執行結果正確且不超時
- (第一次提交)用最直覺的方法兩層 for 迴圈，結果超時
- (第二次提交)此方法採 bit-by-bit 的觀點來實作
```c=
int totalHammingDistance(int* nums, int numsSize){
int total = 0;
for (int i = 0; i < 31; i++) {
int oneCount = 0;
for (int j = 0; j < numsSize; j++) {
if (((1 << i) & nums[j]) != 0)
oneCount++;
}
total += oneCount * (numsSize - oneCount);
}
return total;
}
```
假設在某一位元共有 `oneCount` 個數字為1，那麼就有 `(n - oneCount)` 個數字為0，因為陣列中的每個數字皆會與其他數字計算過一次 hamming distance，所以就會使 hamming distance 總和增加 `oneCount * (n - oneCount)`。如此一來，遍歷所有位元的總和即為最後的答案。
#### 3. 研讀[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)及[抽象代數的實務應用](https://www.math.sinica.edu.tw/www/file_upload/summer/crypt2017/data/2017/%E4%B8%8A%E8%AA%B2%E8%AC%9B%E7%BE%A9/[20170710][%E6%8A%BD%E8%B1%A1%E4%BB%A3%E6%95%B8%E7%9A%84%E5%AF%A6%E5%8B%99%E6%87%89%E7%94%A8].pdf)，摘錄其中 Hamming Distance 和 Hamming Weight 的描述並重新闡述，舉出實際的 C 程式碼來解說
> - 搭配閱讀 [Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA&feature=youtu.be) 及 [Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE&feature=youtu.be)，你可適度摘錄影片中的素材，但應當清楚標註來源
Hamming weight, 記作 $w_H(x)$, 表示 x 向量有幾個位元為1; 而 Hamming distance, 記作 $d_H(x,x')$, 表示兩個向量有幾個不同的位元，又可透過相加兩向量再取其 hamming weight 得到，因此可以寫成 $w_H(x+x')$ (即 $d_H(x,x')$ = $w_H(x+x')$)。
假設模擬從 sender 取得的16個位元，其中11個 data bits，4個 parity bits:
```c=
char bits[16];
for (int i = 0; i < 16; i++) {
bits[i] = rand()%2;
}
/*output:{1,0,0,0,1,0,1,0,0,1,1,1,0,1,1,0}*/
```
接著針對所有位元為1的作 XOR，會得到:
```c=
int res = 0;
for (int i = 0; i < 16; i++) {
if (bits[i])
res ^= bits[i];
}
/*output: 9*/
```
為了讓上述的 XOR 結果為0，9的二進位為`1001`，因此對第 1 及第 8 個進行位元反轉:
```c=
bits[1] = !bits[1];
bits[8] = !bits[8];
int res = 0;
for (int i = 0; i < 16; i++) {
if (bits[i])
res ^= bits[i];
}
/*output: 0*/
```
接下來我們就可以模擬資料傳送過程中受干擾的情況，例如假設第 10 個位元在傳送中受到干擾，XOR 結果就會得到 10，也就是錯誤的位元，因此可以馬上找到錯誤的位元加以修正:
```c=
bits[10] = !bits[10];
int res = 0;
for (int i = 0; i < 16; i++) {
if (bits[i])
res ^= bits[i];
}
/*output: 10*/
```
#### 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 個節點
```c=
#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);
}
```
### 程式說明
首先，根據 line 10-11及15得知 `obj->parent` 是一個指標的指標，因此 `AAA = int **parent`。
此題的原理: 假設要找某節點的第 k 個祖先，k = 3 (= $2^0+2^1$) 為例，那麼意同於找此節點的第 $2^0$ 個祖先的第 $2^1$ 個祖先。
> **為甚麼要這樣做?**
> 因為 n 個點的樹在最差的情況下有 n-1 個祖先，若將每個節點從第 0 到第 n-1 個祖先記錄下來，則需要 O($n^2$) 的空間，但取得第 k 個祖先只需要 O(1) 的時間。
>
> 相反的，若不額外記錄各節點的祖先，時間複雜度就會提高。因此本方法能在時間與空間取一個平衡 - 僅記錄第 $2^0$、$2^1$、...、$2^n$ 個祖先。
obj->parent[i][j] 的意義就是第 i 個節點的第 $2^j$ 個祖先是誰，所以 line 14-20 就在對此二維陣列初始化及設定每個節點的第一個祖先。
接著，line 22-31 建立每個節點 i 的第 $2^j$ 個祖先，會先看此節點是否存在第 $2^{j-1}$ 個祖先，
- 若不存在，則此節點必不存在第 $2^j$ 個祖先;
- 若存在，則此節點的第 $2^j$ 個祖先 = 此節點的第 $2^{j-1}$ 個祖先的第 $2^{j-1}$ 個祖先，因此 `BBB = -1`。
最後呼叫 `treeAncestorGetKthAncestor` 時，根據上述第二段的原理去拆解 k ，因此 `CCC = 1 << i`。
### 延伸問題
#### 1. 指出可改進的地方，並實作對應的程式碼
- Compile error
在 `TreeAncestor` struct 中，新增 `int n;`
```c=
typedef struct {
...
int n;
} TreeAncestor;
```
並在 `treeAncestorCreate` 中，新增 `obj->n = n;`
```c=
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->parent = malloc(n * sizeof(int *));
obj->n = n;
}
```
- 減少使用的記憶體
在原本的程式碼中，之所以 `max_level = 32 - __builtin_clz(n) + 1;` 需要 `+1` ，為的就是多額外配置空間給 obj->parent[i] ，好讓底下 line 22 的 `for` 不會越界存取。(因為這裡 `for` 是靠 `quit` 來離開迴圈的)
也就是說若新增 for 的中止條件，就不用擔心越界，也不需要配置額外空間，來達到節省記憶體的目的。
因此，修改後的部分程式碼如下:
```c=
TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)
{
...
int max_level = 32 - __builtin_clz(n); // remove +1
...
for (int j = 1; j < max_level; j++) { // add j < max_level
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; // remove +1
return obj;
}
```
修改前的程式碼需要 70.3 MB 的記憶體空間，而修改過後只需 68.5 MB，減少了 1.8 MB。
#### 3. 在 LeetCode [1483. Kth Ancestor of a Tree Node](https://leetcode.com/problems/kth-ancestor-of-a-tree-node/) 提交你的實作，你應該要在 C 語言項目中，執行時間領先 75% 的提交者
--------------------------------------
## 測驗3: [FizzBuzz](https://en.wikipedia.org/wiki/Fizz_buzz)
考慮貌似簡單卻蘊含實作深度的 FizzBuzz 題目:
- 從 1 數到 n，如果是 3的倍數，印出 “Fizz”
- 如果是 5 的倍數，印出 “Buzz”
- 如果是 15 的倍數，印出 “FizzBuzz”
- 如果都不是，就印出數字本身
直覺的實作程式碼如下: (`naive.c`)
```c=
#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
考慮下方程式碼:
```c=
#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 題意:
```c=
string literal: "fizzbuzz%u"
offset: 0 4 8
```
以下是利用 bitwise 和上述技巧實作的 FizzBuzz 程式碼: (`bitwise.c`)
```c=
#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)。
### 程式說明
首先，回顧一下 quiz 2 所學的[快速 mod 運算](https://hackmd.io/JMzU3vDsRYuavmBRvpPjDA#%E6%B8%AC%E9%A9%973-%E5%BF%AB%E9%80%9Fmod%E9%81%8B%E7%AE%97)即可了解 line 3-4, 7-8 及 12-13 的原理，在此不贅述。
根據題目給的提示可以整理成下列四種可能:
| 被n整除 | start | length |
| ------ | ----- | ------ |
| n = 3 | 0 | 4 |
| n = 5 | 4 | 4 |
| n = 15 | 0 | 8 |
| X | 8 | 2 |
(X:不被3或5整除)
再回頭看程式碼，在 line 12-13，`div3` 及 `div5` 若為 1，代表 `i` 分別被 3 跟 5 整除，否則為0，於是根據上面表格可以推算出 `length = (2 << div3) << div5`。
處理完 `length` 接著換 `start`。在 line 17，此處`(MSG_LEN >> KK1) >> (KK2 << KK3)`即為 `start`，一樣根據上表，即可推得 `KK1 = div5`, `KK2 = div3`, `KK3 = 2`。
### 延伸問題
#### 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) x $2^n$, n from 1 to 14
給定 `size_t offset`，試著改善原本運算:
```c=
#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 編譯)
```c=
#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 可能形如:
```c=
case 2: blockidx /= 2;
break;
```
這樣的組合，請用最少的 case-break 敘述做出同等`size_t blockidx = offset / PAGE_QUEUES;` 效果的程式碼。
### 程式說明
此方法原理就是先對被除數以及除數同時右移 `ffs32(divident)`位元，剩下的運算再交給 case 處理。
| divident(dec) | divident(binary) | divident >> ffs(divident) |
| -------- | ------------------------- | ----- |
| 1*$2^n$ | 00010...0 | 0001=1 |
| 2*$2^n$ | 00100...0 | 0001=1 |
| 3*$2^n$ | 00110...0 | 0011=3 |
| 4*$2^n$ | 01000...0 | 0001=1 |
| 5*$2^n$ | 01010...0 | 0101=5 |
| 6*$2^n$ | 01100...0 | 0011=3 |
| 7*$2^n$ | 01110...0 | 0111=7 |
| 8*$2^n$ | 10000...0 | 0001=1 |
根據上面張表可得知 CASES 至少需要包含 1, 3, 5, 7 這四個數字，但又因為任何數除以 1 還是原數，所以只需 3, 5, 7 三數即可。
### 延伸問題
#### 1. 練習 LeetCode [51. N-Queens](https://leetcode.com/problems/n-queens/)，應選擇 C 語言並善用上述的 `__builtin_ffs`，大幅降低記憶體開銷
```c=
int ways[] = {1, 1, 0, 0, 2, 10, 4, 40, 92, 352,
724, 2680, 14200, 73712, 365596, 2279184, 14772512,
95815104, 666090624};
int *QueenPos;
int ***res;
int count = 0;
void StoreAnswer(int n)
{
char* queen = malloc((n + 1) * sizeof(char));
queen[n] = '\0';
for (int i = 0; i< n; i++){
for(int j = 0; j< n; j++){
queen[j] = (QueenPos[i] == j) ? 'Q' : '.';
}
memcpy(res[count][i], queen, n + 1);
}
free(queen);
count++;
}
bool checkQueen(int row, int col)
{
for (int i = 0; i < row; i++) {
if (col == QueenPos[i] || abs(col - QueenPos[i]) == abs(row - i))
return false;
}
return true;
}
void NQueens(int row, int n)
{
if (count == ways[n])
return;
for (int j = 0; j < n; j++) {
if (checkQueen(row, j)) {
QueenPos[row] = j;
if (row == n - 1)
StoreAnswer(n);
else
NQueens(row + 1, n);
}
}
}
char ***solveNQueens(int n, int *returnSize, int **returnColumnSizes)
{
*returnSize = ways[n];
*returnColumnSizes = malloc(ways[n] * sizeof(int));
for (int i = 0; i < ways[n]; i++) {
(*returnColumnSizes)[i] = n;
}
QueenPos = malloc(n * sizeof(int));
res = malloc(ways[n] * sizeof(char **));
for (int i = 0; i < ways[n]; i++) {
res[i] = malloc(n * sizeof(char *));
}
for (int i = 0; i < ways[n]; i++) {
for (int j = 0; j < n; j++) {
res[i][j] = malloc((n + 1) * sizeof(char));
}
}
NQueens(0, n);
count=0;
return res;
}
```
程式說明:
- 大致流程(可搭配下面的圖來看):
- 從第0列開始，一列一列往下看。
- 每一列中，由左至右一行一行看，透過呼叫 `CheckQueen` 檢查是否 Queen 可以放在此位置
- 若可以，則遞迴的往下一列去看(即`NQueens(row+1)`)
- 這裡還要檢查是否為最後一列，若是，則以找到其中一種棋盤擺放方式，呼叫 `PushAnswer` 將結果存入 `res`
- 若已找到全部的擺放方式，則 return
```graphviz
digraph{
node [shape = record]
n1[label="{Q|x|x|x}|{x|x||}|{x||x|}|{x|||x}"]
n2[label="{x|Q|x|x}|{x|x|x|}|{|x||x}|{|x||}"]
n3[label="{x|x|Q|x}|{|x|x|x}|{x||x|}|{||x|}"]
n4[label="{x|x|x|Q}|{||x|x}|{|x||x}|{x|||x}"]
n1302[label="{Q|x|x|x}|{x|x|x|Q}|{x|Q|x|x}|{x|x|x|x}" color = gray]
n14[label="{Q|x|x|x}|{x|x||x}|{x|x|x|}|{x|Q|x|x}"]
n24[label="{x|x||}|{Q|x|x|x}|{x|x|x|}|{x|Q|x|x}"]
n31[label="{x|Q|x|x}|{x|x|x|}|{Q|x|x|x}|{x|x||}"]
n41[label="{x|Q|x|x}|{x|x|x|}|{x|x||x}|{Q|x|x|x}"]
n4203[label="{x|x|x|x}|{x|Q|x|x}|{x|x|x|Q}|{Q|x|x|x}" color = gray]
n1420[label="{Q|x|x|x}|{x|x|Q|x}|{x|x|x|x}|{x|Q|x|x}" color = gray]
n1403[label="{Q|x|x|x}|{x|x|x|x}|{x|x|x|Q}|{x|Q|x|x}" color = gray]
n2413[label="{x|x|Q|x}|{Q|x|x|x}|{x|x|x|Q}|{x|Q|x|x}" color= red]
n2401[label="{x|x|x|Q}|{Q|x|x|x}|{x|x|x|x}|{x|Q|x|x}" color = gray]
n3142[label="{x|Q|x|x}|{x|x|x|Q}|{Q|x|x|x}|{x|x|Q|x}" color= red]
n3104[label="{x|Q|x|x}|{x|x|x|x}|{Q|x|x|x}|{x|x|x|Q}" color = gray]
n4130[label="{x|Q|x|x}|{x|x|x|x}|{x|x|Q|x}|{Q|x|x|x}" color = gray]
n4102[label="{x|Q|x|x}|{x|x|x|Q}|{x|x|x|x}|{Q|x|x|x}" color = gray]
root->n1->n1302
n1->n14->n1420
n14->n1403
root->n2->n24->n2413
n24->n2401
root->n3->n31->n3142
n31->n3104
root->n4->n41->n4130
n41->n4102
n4->n4203
}
```
- `***solveNQueens(int n, int *returnSize, int **returnColumnSizes)`
- `*returnSize`: 記錄 `res` 的 2D array 數量(即 `ways[n]`)
- `**returnColumnSizes`: 記錄每個 2D array 的行數(即 `n`)
- `QueenPos`: 記錄各列 Queen 所在的行數(即 QueenPos[1]=3 代表 Queen在第一列第三行)
- `***res`: 記錄每個答案的棋盤擺放方式
- `NQueens(int row, int n)`
- 主要就是**遞迴**的去找可能的擺放方式
- line 34-35 用來判斷是否已找到全部擺放方式
- `checkQueen(int row, int col)`
- 檢查該 `row` 以上的所有格子看是否已存在 Queen 使得
1. 與 `col` 同一行 或
2. 在 `(row, col)` 的右上或左上
- 若都沒有，代表 `(row, col)` 可以放 Queen，反之，則不行放
- `StoreAnswer(int n)`
- 根據 `QueenPos` 將一種擺放方式存到 `res` 中
- 看過所有 n x n 個格子，若該格有擺放 Queen，則為 `'Q'`，否則為 `'.'`
Sign in with Wallet
Connect another wallet