# 2020q3 Homework7 (quiz7)
contributed by < `ccs100203` >
###### tags: `linux2020`
> [第 7 週測驗題](https://hackmd.io/@sysprog/2020-quiz7)
## 測驗 1
選出何者為 [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);
}
```
Tail recursion 的好處在於程式不需要完全保留上一層 stack 的資訊，可以把他視為一個 for loop 使用，如此一來 stack 的增長就會比原本的 recursion 方式還慢，更省空間也更不容易 stackoverflow。
- funA
不是 Tail recursion，原因在 `return 5 * funcA(i - 1);`，由於這邊多做了乘法運算，導致程式必須保留住上一層 stack 的資訊，為了讓程式在 `return` 回來後能夠做 `5 * funcA` 的運算，以至於無法提早從 stack pop 掉。
- funB
是 Tail recursion，在 `return funcB(i - 1);` 時，程式會在當前的 stack 得到想要的運算結果才進入下一層 stack，程式並不需要在 `return` 回來後額外做運算，代表之前的 stack 的內容除了 return address 外不再會用到，所以對此程式可以做優化，提早 pop 掉之前 stack 的內容以節省空間。
## 測驗 2
考慮測試 C 編譯器 [Tail Call Optimization (TCO)](https://en.wikipedia.org/wiki/Tail_call) 能力的程式 [tco-test](https://github.com/sysprog21/tco-test)
從實驗中可發現下方程式無法對 g 函式施加 TCO:
```cpp
void g(int *p);
void f(void) {
int x = 3;
g(&x);
}
void g(int *p) { printf("%d\n", *p); }
```
因為函式 f 的區域變數 x 在返回後就不再存在於 stack。考慮以下程式碼:
```cpp=
int *global_var;
void f(void)
{
int x = 3;
global_var = &x;
...
/* Can the compiler perform TCO here? */
g();
}
```
下方的程式碼，如果 `g` 沒有對 `global_var` 指標作 `dereference`，那麼就可以提前從 stack pop 掉 `f` 內的資料。反之，如果需要用 `global_var` 代表他需要讀取 `x`，如果提前把 `f` 內的資料 pop 掉就會讀取不到而出現問題。
## 測驗 3
[LeetCode 226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
題目要對 binary tree 做 mirror
```cpp=
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;
}
```
程式的原理就是對子節點做左右交換，一直到每一個 node 都被交換過就會停止。
所以先換左子樹或右子樹對程式並不會有任何影響。
給定
最一開始會先交換 2 跟 3，此時程式執行到第 11 行，會發現左半邊跟右半邊交換了。
再來看到第 12~13 行，這時候只是選擇要從左邊 (紅色框框) 還是右邊 (綠色框框) 先執行而已，所以兩者的順序並不會造成影響。
## 測驗 4
[LeetCoee 201. Bitwise AND of Numbers Range](https://leetcode.com/problems/bitwise-and-of-numbers-range/)
Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.
給定兩個正整數，將 m 跟 n 之間的所有數字做 AND 運算。
```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 & ~((1U << count) - 1);
}
```
利用 `n` 跟 `m` 的差距 `diff`，可以知道哪些 bit 是不需要考慮的。因為從 $m+1, m+2...m+diff$，在運算這些數字時，`diff` 範圍內的每一個 bit 一定都會在 0 跟 1 之間轉換。那麼在 `AND` 過後這些全部會變成 0，所以不需要考慮。
舉例來說 6~9，`32U - __builtin_clz(diff)` 等於 2，代表最小的兩個 bit 不須考慮，因為在運算過程中這些 bit 一定會在某個數字變成 0。
| | 3 | 2 | 1 | 0 |
| :-: | :-: | :-: | :-: | :-: |
| 6 | 0 | 1 | 1 | 0 |
| 7 | 0 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 |
| 9 | 1 | 0 | 0 | 1 |
|diff| 0 | 0 | 1 | 1 |
了解原理後要來設計 mask，假設 $n - m = k, k > 0$，藉由 `32U - __builtin_clz(k)` 得到 `k` 總共有多少個位數 `count`，也可以等價於 $\lfloor log_{2}{k} \rfloor +1$。代表從 LSB 開始有 `count` 個 bit 需要被設計成 0，其他為 1。mask 就可以設計成 $\underbrace{11...11}_\text{32 - count}\underbrace{0...00}_\text{count}$ 的樣子。
假設 `count` 為 2
| | 3 | 2 | 1 | 0 |
| :-: | :-: | :-: | :-: | :-: |
| `count` | 0 | 0 | 1 | 0 |
| `1U << count` | 0 | 1 | 0 | 0 |
| `(1U << count)-1` | 0 | 0 | 1 | 1 |
|`~((1U << count)-1)`<br>**mask**| 1 | 1 | 0 | 0 |
## 測驗 5
[LeetCode 97. Interleaving String](https://leetcode.com/problems/interleaving-string/)
判斷給定的字串 s1 與 s2 可否交錯形成字串 s3。從上圖可見，走訪 s3 所有字元，其字元必定是來自 s1 或來自 s2，並且 s1 與 s2 的字元也是依序取出，也就是 s3[i3] 必定為 s1[i1] 或 s2[i2]，其中 i1, i2, i3 分別為 s1, s2, s3 目前的位置。
```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 = 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];
}
```
TODO
Sign in with Wallet
Connect another wallet