# 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; } ``` ![](https://i.imgur.com/utnf6Mc.png) 假設在某一位元共有 `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; } ``` ![](https://i.imgur.com/FOmJocN.png) 修改前的程式碼需要 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% 的提交者 -------------------------------------- ![](https://i.imgur.com/s6Ckfns.png) ## 測驗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'`，否則為 `'.'`
Last changed by  
 
JimmyLiu0530
340

Read more

台灣萬萬稅

報稅懶人包

12/17/2023
CS:APP 第一章重點整理 - Introduction

contributed by < JimmyLiu0530 > {%hackmd BJrTq20hE %} 課程錄影 (Fall 2015) 課程錄影(中英字幕) 課程介紹 (Spring 2021) 概述 CS:APP 在一開始利用所有新手程式員學的第一支程式，即在螢幕上輸出 hello world，來展示程式從被產出、執行、結束的過程，也幾乎都有點到了各章節的重點，因此接下來內容的範例幾乎都是以 hello.c 為主。

3/11/2022
GDB介紹

{%hackmd BJrTq20hE %} 最簡單方便的除錯工具不外乎是列印指令 (e.g., printf)，但是設想下以下的情況： 某個迴圈可能在第一百萬零七十三次才出錯，這當中印出來的 debug 資料可能多到令人頭昏。因此我們需要一個工具，讓我們可以一邊執行你的程式, 一邊視需要將它停下來觀察當中某些變數的變化。如果發現問題不在此處，還可以叫它繼續執行。執行到一半，還可以手動修改變數的值，看看如果這個問題解決了，下個又在何處，一口氣解決好幾個問題。這些就是 debugger 的工作。 GDB 一種命令列模式的 debugger。若以下列語言撰寫程式 C, objective C, C++, Fortran, Pascal, Ada, ... 等等，而且採用的編譯器是來自 gnu，那麼就可以拿 GDB 來除錯。 使用方法 (以 c 程式舉例) 首先在編譯程式時，需要加上 -g 參數，以便編譯器將除錯資訊加入到程式裡:

3/11/2022
Ubuntu 20.04 wifi 選項消失之解決方法

{%hackmd BJrTq20hE %} 發生原因：如果 windows 中 wifi 可用，但在 Ubuntu 下不可用，那麼及有可能是無線網卡的驅動程式損壞或是消失。因此我們接下來要手動將驅動程式安裝回來。 首先，打開 terminal 使用命令查詢網卡的狀態 $ lshw -C network 得到類似的訊息如下：

3/11/2022
Read more from JimmyLiu0530
Published on HackMD