--- tags: 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統 --- # 2020q3 Homework7 (quiz7) contributed by < `RusselCK` > ###### tags: `RusselCK` > [ bitwise 操作 ＆ 遞迴呼叫 ＆ 編譯器最佳化 練習題](https://hackmd.io/@sysprog/2020-quiz7) ## Q1. 判斷 是否為 [Tail Recursion](https://en.wikipedia.org/wiki/Tail_call) ```cpp= int funcA(int i) { if (i == 0) return 0; return 5 * funcA(i - 1); } int funcB(int i) { if (i == 0) return 0; return funcB(i - 1); } ``` :::info * Tail call 指的是一個函式的最後一條語句也是一個返回呼用函式的語句 * 即這個呼叫的返回值直接被當前函式返回的情形 * 在函式體末尾被返回的可以是對另一個函式的呼叫，也可以是對自身呼叫 * 若這個函式在尾位置呼叫本身（或是一個尾呼叫本身的其他函式等等），則稱這種情況為 Tail Recurtion ::: - 程式碼解析 * `#12`: `funcB(i)` 的最後一句 是 `return funcB(i - 1);` * 呼叫本身，符合 Tail Recurtion 的定義 * 編譯器 可以做 Tail Call Optimization, TCO ```graphviz digraph{ rankdir = LR step1[shape = record label= "funcB(i)"] step2[shape = record label= "funcB(i)|funcB(i-1)"] step3[shape = record label= "funcB(i)|funcB(i-1)|funcB(i-2)"] step1 -> step2 -> step3 } ``` * function call 原本的佔用 stack 情形 ```graphviz digraph{ rankdir = LR step1[shape = record label= "funcB(i)"] step2[shape = record label= "funcB(i-1)"] step3[shape = record label= "funcB(i-2)"] step1 -> step2 -> step3 } ``` * 以 `funcB(i)` 來說，執行到 `return funcB(i - 1)` 後，接下來只要等 `funcB(i - 1)` 的回傳值就可以了 * 也就是說 `funcB(i)` 已經做完了，不需要再留 stack space 給 `funcB(i)` * 藉此達到省 stack space 的效果 - `#5` : `funcA(i)` 的最後一句 為 `return 5 * funcA(i - 1);` - 需要等 `funcA(i - 1)` 回傳 再 乘上 5 ，才是真正的返回值 - 不符合 Tail Recurtion 的定義 - 編譯器無法對其做 TCO ## Q2. ## Q3. LeetCode [226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/) ![](https://i.imgur.com/chni5ov.png) ```cpp= struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }; struct TreeNode *invertTree(struct TreeNode *root) { if (!root) return NULL; if (!root->left && !root->right) return root; struct TreeNode *tmp = root->left; root->left = root->right; root->right = tmp; invertTree(root->left); invertTree(root->right); return root; } ``` * 程式碼解析： ```cpp=9 if (!root) return NULL; ``` * 若為 空樹，回傳 NULL ```cpp=12 if (!root->left && !root->right) return root; ``` * 若左右都無子樹，可直接回傳 `root` ```cpp=15 struct TreeNode *tmp = root->left; root->left = root->right; root->right = tmp; ``` * 將 左、右子樹 交換位置 ```cpp=18 invertTree(root->left); invertTree(root->right); ``` * 左、右子樹 分別遞迴作 `invertTree` * 先後順序不影響結果 ## Q4. LeetCoee [201. Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/) * Given a range $[m, n]$ where $0 \leq m \leq n \leq 2147483647$, return the bitwise AND of all numbers in this range, inclusive. [解法 I](https://hackmd.io/@Zero871015/LeetCode-201) : ```cpp= int rangeBitwiseAnd(int m, int n) { if (m == 0) return 0; int diff = n - m; int count = diff ? 32U - __builtin_clz(diff) : 0; return m & n & MASK; // MASK = ~((1U << count) - 1) } ``` | | Decimal | Binary | |:-----:|:-------:|:---------:| | m | 100 | ==011==0 0100 | | n | 120 | ==011==1 1000 | | m & n | | ==011==0 0000 | | n - m | 20 | 0001 0100 | |Mask|`~((1U << 5) - 1)` | 1110 0000| | Decimal | Binary | Decimal | Binary | Decimal | Binary | |:-------:|:---------:|:-------:|:---------:|:-------:|:---------:| | | | 8 | 0000 1000 | 16 | 0001 0000 | | 1 | 0000 0001 | 9 | 0000 1001 | 17 | 0001 0001 | | 2 | 0000 0010 | 10 | 0000 1010 | 18 | 0001 0010 | | 3 | 0000 0011 | 11 | 0000 1011 | 19 | 0001 0011 | | 4 | 0000 0100 | 12 | 0000 1100 | 20 | 0001 0100 | | 5 | 0000 0101 | 13 | 0000 1101 | | | | 6 | 0000 0110 | 14 | 0000 1110 | | | | 7 | 0000 0111 | 15 | 0000 1111 | | | * 題目要求為 $m$ & $(m+1)$ & ... & $(n-1)$ & $n$ * `m & n` 可以得知 結果之較大位數的 bits ( 第一個表格畫螢光的部份 ) * 接著我們還缺少的是，剩餘的 bits 應該為多少？ * 以上方例子來看， `m`、`n` 相差 20 * 由第二個表格可知 1 & 2 & ...& 20 = 000==0 0000== * 且能保證 後 5 個 bits 結果 必為 0 * `8 - __builtin_clz(20)` = 8 - 3 = 5 * 因此，我們還須要一個 Mask = 1110 0000 = ~( 0001 1111 ) = ~( (0010 0000) - 1 ) = ~( (1 << 5) - 1 ) * 故 **MASK = `~((1U << count) - 1)`** ## Q5. LeetCode [97. Interleaving String](https://leetcode.com/problems/interleaving-string/) ![](https://i.imgur.com/UJyMQmZ.png) #### [解法 I](https://medium.com/@bill800227/leetcode-97-interleaving-string-18b1202fb0ea) : [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming) ```cpp= bool isInterleave(char * s1, char * s2, char * s3){ size_t n = strlen(s1), m = strlen(s2); if ((n + m) != strlen(s3)) return false; bool dp[n+1][m+1]; for (int i = 0; i < (n + 1); ++i ) memset(dp[i], false, (m + 1)); dp[0][0] = 1; for(int i = 1; i < (n + 1); ++i) dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); for(int j = 1; j < (m + 1); ++j) dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]); for(int i = 1; i < (n + 1); ++i){ for(int j = 1; j < (m + 1); ++j){ dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1])); } } return dp[n][m]; } ``` | $s_1$ \ $s_2$ | | d | b | b | c | a | | -------------:|:---:|:---:|:---:|:---:| --- |:---:| | | 1 | 0 | 0 | 0 | 0 | 0 | | a | 1 | 0 | 0 | 0 | 0 | 0 | | a | 1 | 1 | 1 | 1 | 1 | 0 | | b | 0 | 1 | 1 | 0 | 1 | 0 | | c | 0 | 0 | 1 | 1 | 1 | 1 | | c | 0 | 0 | 0 | 0 | 0 | 1 | * `DP[i][j]` : `s1[0:i-1]` 與 `s2[0:j-1]` 是否能組成 `s3[0:i+j-1]` * 程式碼解析： ```cpp=3 size_t n = strlen(s1), m = strlen(s2); if ((n + m) != strlen(s3)) return false; ``` * 先確定 `s1` + `s2` 的長度是否等於 `s3` 的長度 ```cpp= bool dp[n+1][m+1]; for (int i = 0; i < (n + 1); ++i ) memset(dp[i], false, (m + 1)); dp[0][0] = 1; ``` * 建立 DP 表格，並設置 `dp[0][0]` 為 1，其餘為 0 * [效能評估](https://leetcode.com/submissions/detail/414107932/)： ![](https://i.imgur.com/w0nAG7c.png) #### 解法 II : DP with 1D Array ```cpp= bool isInterleave(char *s1, char *s2, char *s3) { size_t n = strlen(s1), m = strlen(s2); if ((n + m) != strlen(s3)) return false; bool dp[m + 1]; memset(dp + 1, false, m * sizeof(bool)); dp[0] = true; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 && j == 0) continue; int p = RRR; // RRR = i + j - 1 if (i == 0) dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]); else { dp[j] &= (s1[i - 1] == s3[p]); if (j > 0) dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]); } } } return dp[m]; } ``` * 對 解法 I 進行的修改： * `dp` array 由 2D 改為 1D * 將 解法 I 的表格 一列一列計算完成並覆蓋舊資料 * 將三個 `for` 迴圈 合併成 一個 * 程式碼解析： ```cpp=11 for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 && j == 0) continue; int p = RRR; if (i == 0) dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]); else { dp[j] &= (s1[i - 1] == s3[p]); if (j > 0) dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]); } } } ``` * `#16`、`#17` 等價於 解法 I 的 ```cpp=15 for(int j = 1; j < (m + 1); ++j) dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]); ``` * `#19` 等價於 解法 I 的 ```cpp=12 for(int i = 1; i < (n + 1); ++i) dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]); ``` * `#20`、`#21` 等價於 解法 I 的 ```cpp=21 dp[i][j] = (dp[i - 1][j] && (s1[i - 1] == s3[i + j - 1])) || (dp[i][j - 1] && (s2[j - 1] == s3[i + j - 1])); ``` * 故 **RRR = i + j - 1** * [效能評估](https://leetcode.com/submissions/detail/414112144/): ![](https://i.imgur.com/kqpxhPd.png) * 與 解法 I 沒什麼區別 * 或許可將 dp 改用 Bit Array 儲存 ## Q5. 進階題 #### 解法 III : DP with Bit Array ```cpp __uint128_t MAX = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF; bool isInterleave(char *s1, char *s2, char *s3) { size_t n = strlen(s1), m = strlen(s2); if ((n + m) != strlen(s3)) return false; __uint128_t dp = 1; for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (i == 0 && j == 0) continue; int p = i + j -1; __uint128_t mask = MAX ^ ((__uint128_t)1 << j); if (i == 0){ __uint128_t set = (1U & (dp >> (j - 1))) & (s2[j - 1] == s3[p]); dp = (dp & mask) | (set << j); // dp[j] = dp[j - 1] & (s2[j - 1] == s3[p]); } else { __uint128_t set = (s1[i - 1] == s3[p]); dp &= mask | (set << j); // dp[j] &= (s1[i - 1] == s3[p]); if (j > 0){ set = (1U & (dp >> (j - 1))) & (s2[j - 1] == s3[p]); dp |= (set << j); // dp[j] |= dp[j - 1] & (s2[j - 1] == s3[p]); } } } } return (dp >> m); } ``` * [效能評估](https://leetcode.com/submissions/detail/414854880/)： ![](https://i.imgur.com/SNCYGtS.png)
Last changed by  
 
RusselCK
116

Read more

VSCode 套件安裝

C 語言開發 MinGW mingw-get-setup.exe mingw32-gcc-g++-bin mingw32-gdb-bin 檔案總管 > 電腦 > 內容 > 進階系統設定 > 環境變數 > Path 加入 \MinGW\bin

8/7/2022
ARGB To BW

contributed by < RusselCK > tags: RusselCK 【目標】 [ ] 2020q3 第 10 週測驗題 - 測驗 1 rgba.bng bw.png

10/2/2021
深入淺出物件導向分析與設計 筆記

範例程式碼 先修班 Chapter 0 歡迎光臨物件村 基礎篇 Chapter 1 偉大軟體的三步驟 Chapter 2 收集客戶需求

9/8/2021
TCL 讀書會(?

[x] TCL 教學 [x] TCL vscode 套件 Jimmy Mac VSCode 寫 C/C++ 教學 codechef jimmy helloworld.c

7/14/2021
Read more from RusselCK
Published on HackMD