# 2020q3 Homework4 (quiz4)
contributed by < `nelsonlai1` >
## 測驗 1
```c=
int hammingDistance(int x, int y) {
return __builtin_popcount(x OP y);
}
```
這題要算兩數間的 Hamming distance，而 XOR 後在原本相異的位元會變成 1，再用 popcount 就能算出 Hamming distance。
### 延伸問題
#### 1. 舉出不使用 gcc extension 的 C99 實作程式碼
```c=
int hammingDistance(int x, int y){
int result = 0;
for (int i = 0; i < 31; i++)
result += ((x >> i) & 1) ^ ((y >> i) & 1);
return result;
}
```
#### 2. 練習 LeetCode 477. Total Hamming Distance
```c=
int totalHammingDistance(int* nums, int numsSize){
int result = 0, ones = 0;
for (int i = 0; i < 30 ; i++) {
for (int j = 0; j < numsSize; j++) {
ones += ((nums[j] >> i) & 1);
}
result += ones * (numsSize - ones);
ones = 0;
}
return result;
}
```
這題最直接的方法應該是計算每對數字的 Hamming distance 再加起來，不過這樣就會超時了，所以要換一種解法。
當兩個數在同一個位元上有差別時才會產生 Hamming distance，而當 x + y 個數在同一個位元上有 x 個 1，y 個 0 時，這個位元能造成的 Hamming distance 是 x * y。
題目敘述中提到陣列中的數不超過 10^9，所以只檢查 30 個位元。計算每個位元共有多少 1 跟 0，再相乘後加到結果中，就能得到答案。
#### 3. ECC & Hamming distance, Hamming weight
[錯誤更正碼簡介](https://w3.math.sinica.edu.tw/math_media/d184/18404.pdf)中提到在資料傳輸時，可能會有干擾訊號形成錯誤。而錯誤更正碼的精神是在傳輸前先對資料做處理，以這裡介紹的方法為例，是在原本的資料上加上幾個額外的 bits。如此一來，只要錯誤小於一定的數量，就能夠更正回來。
Hamming distance : 兩個數間不一樣的 bits 有幾個。
Hamming weight : 一個數裡面 1-bits 有幾個 (popcount)。
裡面提到 x 和 x' 的 Hamming distance 是 x + x' 的 Hamming weight，其實就是本題的做法(文章中的加法指的是 XOR 運算)
[Hamming codes, Part I](https://www.youtube.com/watch?v=X8jsijhllIA) 較容易理解，裡面提到一種叫做 Hamming code 的錯誤更正碼，可以改正一個錯誤 bits。
以 (15, 11)Hamming code (15 個 bits 中帶有 11 個有內容的 bits) 為例，
| 0 | 1 | 2 | 3 |
| - | - | - | - |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10| 11|
| 12| 13| 14| 15|
第 1, 2, 4, 8 bits 作為 redundant bits，檢查錯誤用，第 0 個 bit 無作用(或是在 extended Hamming code 中檢查整體的 1-bits 是否為偶數)。
第 1, 2, 4, 8 bits 的值依照底下這張圖的規則來填入值，分別計算 Q1 ~ Q4 中藍色區塊的 1-bits 數量並調整第 1, 2, 4, 8 bits 的值來讓每個藍色區塊中的 1-bits 為偶數。
當有一個錯誤發生時，便能透過檢查每個藍色區域中的 1-bits 數來找到錯誤發生的 bits。Q1, Q2 用來找到特定的 column，Q3, Q4 用來找特定的 row。
從圖中可以發現第 0 bit 不會被檢查到，所以無從判斷有沒有錯誤，為了解決第 0 bits 沒有用到的問題，extended Hamming code 會計算整體的 1-bits 數，並且調整第 0 bit 的值來讓整體的 1-bits 為偶數。這樣一來，如果有兩個或偶數個錯誤發生時，會觀察到整體的 1-bits 是偶數，但檢查藍色區域時會發現有錯，這時就能判斷傳輸時產生了偶數個錯誤。雖然不能更正錯誤，但可以發現錯誤並要求傳送端重新傳送。
[Hamming codes, Part II](https://www.youtube.com/watch?v=b3NxrZOu_CE) 延續 part I 的內容，並說明如何實際寫成程式碼。
這張圖表示 0 ~ 15 (0000 ~ 1111) 可以透過每個 bit 是 1 或 0 來判斷位於上面 Q1 ~ Q4 的哪個位置，假設第 4 個 bits 是 1，則位於 Q1 的藍色區域，反之則位於褐色區域。其他 bits 以此類推。
當一段資料傳來時，將資料中的 1-bits 位置找出來，並且將其全部做 XOR，就可以得到有問題的那個 bits 的位置，如下圖 :
而可以這樣做是因為 XOR 的特性，有偶數個 1-bits 時會輸出 0。
先從計算結果的第四個 bit 看起，第四個 bit 為 0 代表著 Q1 中藍色區域的 1-bits 是偶數，同時代表著有問題的位置在褐色區域，其他 bits 以此類推，所以這個結果正好是有問題的位置。
而如果現在要做 encode 也很類似，一樣將 1-bits 的位置做 XOR，接著調整第 1, 2, 4, 8 bits 的值來讓結果變成 0000。以影片中的 1010 為例子，將 1000 跟 0010 分別對 1 做 XOR(toggle 1 and 0) 就能讓結果變成 0000，因為如果要刪去一個做 XOR 的元素實際上也等同於再 XOR 一次，如圖所示 :
根據以上做法實作的 code :
解碼部分 :
```c=
uint16_t ecc(uint16_t n)
{
int flip = 0;
for (int i = 0; i < 16; i++) {
if ((n >> i) & 1)
flip ^= i;
}
return flip ? n ^ (1 << (15 - flip)) : n;
}
```
編碼 :
```c=
uint16_t encode(uint16_t n)
{
int mod = 0;
uint16_t result = n;
for (int i = 0; i < 16; i++) {
if ((n >> i) & 1)
mod ^= i;
}
while (mod != 0) {
result ^= (1 << (15 - (mod & -mod)));
mod ^= (mod & -mod);
}
return result;
}
```
main function :
```c=
int main()
{
uint16_t ori = 7777;
uint16_t noise, rec;
printf("original message : ");
for (int i = 12; i >=0; i--) {
if (i == 11 || i == 7)
continue;
printf("%d", (ori >> i) & 1);
}
printf("\n");
ori = encode(ori);
noise = ori ^ (1 << 2);
rec = ecc(noise);
printf("received message : ");
for (int i = 12; i >=0; i--) {
if (i == 11 || i == 7)
continue;
printf("%d", (rec >> i) & 1);
}
printf("\n");
}
```
結果 :
```
original message : 11101100001
received message : 11101100001
```
## 測驗2
>給你一棵樹，樹上有 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]]
```
其中 [-1,0,0,1,1,2,2] 代表第 0 到第 6 個 node 的 parent，也就是底下程式碼中的 `int *parent`
```c=
#include <stdlib.h>
typedef struct {
int **parent;
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 - 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;
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 & (1 << i))
node = obj->parent[node][i];
return node;
}
void treeAncestorFree(TreeAncestor *obj)
{
for (int i = 0; i < obj->max_level; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj);
}
```
`TreeAncestor` 這個 structure 中有兩個變數，分別是 `parent` 跟 `max_level`。
`parent` 是一個二維陣列，`parent [i][j]` 代表 i 這個 node 的第 $2^j$ 代祖先。
`max_level` 用來表示 j 的範圍大小，以 7 個節點為例，最大高度是 6，j 範圍是 0~2 ($6 = 2^1 + 2^2$)，所以 `max_level` 是 3。
`TreeAncestor *treeAncestorCreate(int n, int *parent, int parentSize)` 中，
第 14~18 行將 `obj->parent` 做初始化，將每個都設成 -1。
19~20 行將輸入的 parent (第一代祖先)存在 `obj->parent[i][0]` 中。
22~31 行中，`obj->parent[i][j] = obj->parent[i][j - 1] == -1 ? -1 : obj->parent[obj->parent[i][j - 1]][j - 1];` 先判斷 i 節點 $2^{j-1}$ 代祖先是否不存在，不存在的話則 $2^j$ 代也不存在。反之 $2^j$ 代祖先則是 i 節點的 $2^{j-1}$ 代祖先的 $2^{j-1}$ 代祖先。
(這樣講可能有點拗口，可以想像你的曾曾祖父就是你的祖父的祖父。)
quit 則是來判斷若所有節點的第 $2^j$ 代祖先都不存在時，可以提前結束，因為之後的也會不存在。
有了以上概念後，`int treeAncestorGetKthAncestor(TreeAncestor *obj, int node, int k)` 也不難懂了。當要找 node 的第 k 個祖先時，會以類似二進位的方式來搜尋。如果要找第 7 代時，會以
node = node 第 $2^0$ 祖先 -> node = node 第 $2^1$ 祖先 -> node = node 第 $2^2$ 祖先的方式移動 node 最後找到目標節點。
### 延伸問題
在第 13 行計算 max_level 時多加了 1，是因為在第 22~31 行的迴圈使用 quit 作為終止條件，不這樣的話在 worst case (一條直線)下可能會存取到超過 array 範圍，然後就出錯了。因此第一個改動就是把第 22 行加上 `j < max_level`，就可以不用加 1 了。而這裡也可以順便把 `max_level` 這個變數直接用 `obj->max_level` 取代。
第二個可以改的地方是把 row, column 交換。原本需要 `malloc(n * sizeof(int *))` 和
`malloc(obj->max_level * sizeof(int))`，改完後變成 `malloc(obj->max_level * sizeof(int *))` 和 `malloc(n * sizeof(int))`。差別在於 int 大小是 4 bytes，而 int* 大小是 8 bytes。因為 max_level 會比 n 小，所以這樣就能省下一些空間。
另一個好處是可以把原本的
```
for (int i = 0; i < parentSize; i++)
obj->parent[i][0] = parent[i];
```
改成 `obj->parent[0] = parent;` 省下 for 迴圈的時間。
```c=
typedef struct {
int **parent;
int max_level;
} TreeAncestor;
TreeAncestor* treeAncestorCreate(int n, int* parent, int parentSize) {
TreeAncestor *obj = malloc(sizeof(TreeAncestor));
obj->max_level = 32 - __builtin_clz(n);
obj->parent = malloc(obj->max_level * sizeof(int *));
for (int i = 1; i < obj->max_level; i++) {
obj->parent[i] = malloc(n * sizeof(int));
for (int j = 0; j < n; j++)
obj->parent[i][j] = -1;
}
obj->parent[0] = parent;
for (int i = 1; i < obj->max_level; i++) {
int quit = 1;
for (int j = 0; j < n; j++) {
obj->parent[i][j] = obj->parent[i - 1][j] == -1
? -1
: obj->parent[i - 1][obj->parent[i - 1][j]];
if (obj->parent[i][j] != -1) quit = 0;
}
if (quit) break;
}
return obj;
}
int treeAncestorGetKthAncestor(TreeAncestor* obj, int node, int k) {
for (int i = 0; i < obj->max_level && node != -1; i++)
if (k & (1 << i))
node = obj->parent[i][node];
return node;
}
void treeAncestorFree(TreeAncestor* obj) {
for (int i = 0; i < obj->max_level; i++)
free(obj->parent[i]);
free(obj->parent);
free(obj);
}
```
## 測驗3
```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;
}
```
is_divisible 運用了 [quiz2](https://hackmd.io/@sysprog/2020-quiz2#%E6%B8%AC%E9%A9%97-4) 的技巧判斷是否整除，當整除時回傳 1，其他則回傳 0。
length 用來決定要複製多長的字串，
當 i 是 3 或 5 的倍數，且非 15 的倍數時要複製四個字元 (Fizz or Buzz)，
當 i 是 15 的倍數時要複製八個字元 (FizzBuzz)，
其餘則複製兩個字元 (%u)。
所以這裡用 `length = (2 << div3) << div5;` 可以達到目的。
第 17 行可以從前面的敘述中知道，
當 i 是 3 的倍數時，start 要為 0。
當 i 是 5 的倍數且非 15 的倍數時，start 要為 4。
其餘時候 start 要為 8。
可以統整為，當有因數 3 時，MSG_LEN 要右移 3 “以上“，當有因數 5 時，要右移 1。所以 `KK1 = div5`, `KK2 = div3`, `KK3 = 2` 可以達到目的。
### 延伸問題
#### 1. 評估 naive.c 和 bitwise.c 效能落差
根據提示，我把 source code 改成以下 :
naive.c : (`if i % 15 == 0` 不用加)
```c=
int main() {
char buf[20];
for (unsigned int i = 1; i <= 100000000; i++) {
if (i % 3 == 0) sprintf(buf, "Fizz");
if (i % 5 == 0) sprintf(buf, "Buzz");
if ((i % 3) && (i % 5)) sprintf(buf, "%u", i);
}
return 0;
}
```
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;
char buf[20];
int main(int argc, char *argv[]) {
for (size_t i = 1; i <= 100000000; 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 >> div5) >> (div3 << 2)], length);
fmt[length] = '\0';
sprintf(buf, fmt, i);
}
return 0;
}
```
結果 bitwise.c 的結果居然比較慢
```
Performance counter stats for './naive':
3584.62 msec task-clock # 1.000 CPUs utilized
18 context-switches # 0.005 K/sec
0 cpu-migrations # 0.000 K/sec
51 page-faults # 0.014 K/sec
148,7757,0325 cycles # 4.150 GHz
431,0389,3880 instructions # 2.90 insn per cycle
73,3560,5643 branches # 2046.408 M/sec
4543,6601 branch-misses # 0.62% of all branches
3.585121376 seconds time elapsed
3.584910000 seconds user
0.000000000 seconds sys
```
```
Performance counter stats for './bitwise':
5265.99 msec task-clock # 1.000 CPUs utilized
13 context-switches # 0.002 K/sec
0 cpu-migrations # 0.000 K/sec
49 page-faults # 0.009 K/sec
218,8159,0327 cycles # 4.155 GHz
642,2565,2212 instructions # 2.94 insn per cycle
110,4922,7345 branches # 2098.223 M/sec
4712,5830 branch-misses # 0.43% of all branches
5.266343370 seconds time elapsed
5.266260000 seconds user
0.000000000 seconds sys
```
## 測驗4
這題要加速運算 `size_t blockidx = offset / PAGE_QUEUES;` 這行指令。
其中 `PAGE_QUEUES` 可能的值是(1 or 2 or 3 or 4 or 5 or 6 or 7 or 8) × $2^n$, n from 1 to 14。
```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
}
```
`__builtin_ffs(x)` 這個 function 用來表示 x 二進位的最後一個 1 的位置。所以
`((__builtin_ffs(x)) - 1)` 的值等同於 x 的 trailing 0-bits。從第 5,6 行可以看到 blockidx 會先除以 divident(PAGE_QUEUES) 的 2^N 因數，接著 divident 也會把自己的 2^N 因數去除。
而最後的 `switch (divident)` 就是將其餘的因數分 case 做處理(也就是再除以剩下的因數)。由於 PAGE_QUEUES 的範圍是固定的，所以去除 2^N 因數後剩下的因數只有 3, 5, 7 而已。
Sign in with Wallet
Connect another wallet