# 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; } ``` ![](https://i.imgur.com/jE4s550.png) #### 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; } ``` ![](https://i.imgur.com/RM8xmqQ.png) 這題最直接的方法應該是計算每對數字的 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 為偶數。 ![](https://i.imgur.com/tb1UZKh.png =200x) 當有一個錯誤發生時，便能透過檢查每個藍色區域中的 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 的內容，並說明如何實際寫成程式碼。 ![](https://i.imgur.com/l1OUznw.png =500x) 這張圖表示 0 ~ 15 (0000 ~ 1111) 可以透過每個 bit 是 1 或 0 來判斷位於上面 Q1 ~ Q4 的哪個位置，假設第 4 個 bits 是 1，則位於 Q1 的藍色區域，反之則位於褐色區域。其他 bits 以此類推。 當一段資料傳來時，將資料中的 1-bits 位置找出來，並且將其全部做 XOR，就可以得到有問題的那個 bits 的位置，如下圖 : ![](https://i.imgur.com/yusvQnd.png =500x) 而可以這樣做是因為 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 一次，如圖所示 : ![](https://i.imgur.com/XXzu2tL.png =100x) 根據以上做法實作的 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 個節點 ![](https://i.imgur.com/pL1Celk.png) 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); } ``` ![](https://i.imgur.com/nRN1crp.png) ## 測驗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 而已。
Last changed by  
 
nelsonlai1
405

Read more

Floyd's cycle detection

步驟 龜兔同時從起點出發，兔的速度是龜的兩倍，若兩者相遇代表有 cycle 存在。 第一次相遇後，龜回到起點，兔在原地。 龜兔同時出發，但這次速度相同，兩者相遇的地點即是 cycle 開始處。 證明 假設龜速 = 1，兔速 = 2，開頭到 cycle 的距離 = m，cycle 長度 = r 第一次相遇時龜走了 k 步，兔走了 2k 步。 $$

1/18/2021
2020q3 Homework5 (quiz5)

contributed by < nelsonlai1 > 測驗 1 #include <stdio.h> #include <stdlib.h> double divop(double orig, int slots) { if (slots == 1 || orig == 0) return orig; int od = slots & 1;

11/5/2020
2020q3 Homework6 (quiz6)

contributed by < nelsonlai1 > 測驗 1 浮點數結構分為 sign, exponent, fraction 三個部分，而浮點數的值為 $2^{(exponent-127)} \times (1 + fraction)$，且 sign 決定正負號，其中 fraction 的計算是最左邊的 bit 為 $2^{-1}$，第 2 個為 $2^{-2}$，以此類推。 float fp32tobf16(float x) { float y = x; int *py = (int *) &y; unsigned int exp, man;

10/29/2020
2020q3 Homework3 (quiz3)

contributed by < nelsonlai1 > 測驗 1 int asr_i(signed int m, unsigned int n) { const int logical = (((int) -1) OP1) > 0; unsigned int fixu = -(logical & (OP2)); int fix = *(int *) &fixu; return (m >> n) | (fix ^ (fix >> n)); }

10/6/2020
Read more from nelsonlai1
Published on HackMD