---
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/)
```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/)
#### [解法 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/)：
#### 解法 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/):
* 與 解法 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/)：
Sign in with Wallet
Connect another wallet