---
tags: 進階電腦系統理論與實作
---
# 2020q3 Homework7 (quiz7)
contributed by < `RinHizakura` >

> [第 7 週測驗題](https://hackmd.io/@sysprog/2020-quiz7)
> [GitHub](https://github.com/RinHizakura/NCKU-System-Software-Quiz/tree/master/quiz7)
## 測驗 `1`
根據 [Tail call](https://en.wikipedia.org/wiki/Tail_call)，`funcA` 的函式返回值為對自身呼叫的返回值加上另一個數值，因此非 tail recursion; `funcB` 的返回值則是一個對自身的函式呼叫，因此可以直接返回該呼叫的返回結果，為 tail recursion。因此 `T = (b)`。

## 測驗 `2`

根據 [`__builtin_return_address`](https://gcc.gnu.org/onlinedocs/gcc/Return-Address.html)，`__builtin_return_address(0)` 可以印出當前函式所在的 stack 位置。

接下來，觀察 macro 是如何展開的，以 `TCO_RET_TEST("char return to int", ret_int_char, return, int, char, 0)` 為例，注意到 `main.c` 中兩次 include `test.h`，並定義不相同的 `TCO_RET_TEST`，第一個會展開為:

void first_ret_int_char(void);

第二個則會展開為:

printf("%-45s", "char return to int"":");
first_ret_int_char();
check();

在 `first.c` 對應的展開:

char second_ret_int_char(void);                        
                                                       
int first_ret_int_char(void)                           
{                                                      
    first_ra = __builtin_return_address(0);            
    return second_ret_int_char();                      
}

在 `second.c` 對應的展開

char second_ret_int_char(void)                         
{                                                      
    second_ra = __builtin_return_address(0);           
    return 0;                                        
}

則我們可以比對 `first_ra` 和 `second_ra` 得知是否可以做 TCO，因為如果最佳化可行，則 call function 可以不需要產生額外的 stack frame，因此 `first_ra` 和 `second_ra` 可以得到一樣的位址。

:::warning
以前面的例子來說，有想到 `"char return to int"` 無法 TCO 的原因可能是因為拿到的 char 可能會需要額外的 sign extension 處理，因此編譯器不敢貿然做 TCO。但不確定相反的 `"int return to char"` 不可以做 TCO 的主要原因(雖然此行為會導致 overflow，本身就是 undefined behavior?)
:::

:::info
注意到無法做最佳化的原因是因為函式落在不同的 C file 中，因此函式會成為一個獨立的 [Translation unit](https://en.wikipedia.org/wiki/Translation_unit_(programming))，如果刻意去做 [link time optimization](https://gcc.gnu.org/wiki/LinkTimeOptimization)(加上參數 [`-flto`](https://gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html))，則 TCO 就有機會可以實行。
:::

回到原題目，則如果考慮 `f` 和 `g` 被定義在不同的 C file 中，則即使函式 `g` 沒有對 `global_var` 指標作 dereference，但是編譯器無從得知，在不考慮使用 link time optimization 的情境下，編譯器仍無法施加 TCO，因此 `Q = (a)`。

## 測驗 `3`

struct TreeNode *invertTree(struct TreeNode *root)
{ 
    ...
    
    struct TreeNode *tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

考慮程式關鍵部份的運行邏輯
* 第 5 - 7 行是將目前節點的左右「子樹」做交換
* 則表示 8 - 9 行是將「子樹」下的子樹做交換，則先對左子樹或對右子樹操作應無區別
* 因此兩者的交換應不會對輸出產生影響，此題答案為 `P = (b)`

## 測驗 `4`

如題要求兩個數字 `m` 、 `n` (m <= n)範圍間所有數字的 and 結果。我們可以把 `m` 和 `n` 從最高位開始一一比對，直到碰到有差異的 bit 為止，並依據此拆成兩個部份： <font color="#f00">最高位相同</font>的 a bits 及剩餘部份的 b bits(a + b = 32)。

思考把範圍內數字做 and 操作後每個 bit 的結果該為 0 或 1，可以知道對於 `m` 與 `n` 的最高位相同部份，能夠預期範圍的內的數字的那些位元也是相同的;而對於 m 的剩餘部份，其第一個 bit 必定為 0，n 剩餘部份的第一個 bit 必定為 1，因此能夠預期兩個數字的剩餘部份中每個 bit 必定有至少一次出現 0。

考慮 and 操作的特性，我們可以歸納出答案應該是前 a bits 等同<font color="#f00">最高位相同</font>部份，且後 b bits 全為 0 的數字。

| num | binary |
| --- |:----------------------------------- |
| 10 | <font color="#f00">0...01</font>010 |
| 15 | <font color="#f00">0...01</font>111 |
| --- | ----------- |
| ans: 8 | <font color="#f00">0...01</font>000 |

那麼對應演算法的實作，可以先把 `m & n`，這會得到前 a bits 等同最高位相同的部份，後 b bits 不一定的數字。然後我們再透過一個前 a bits 皆為 1，後 b bits 皆為 0 的 mask 做 and 運算，就可以把後 b bits 都設為 0 了。回顧原始程式得知，此 mask 的產生方式應該是 `MASK = (a) ~((1U << count) - 1)`。

附上此程式成功在 leetcode 上提交的結果:

## 測驗 `5`
根據題意，我們可以透過 [Dynamic Programming](https://en.wikipedia.org/wiki/Dynamic_programming) 最直覺的解法是透過一個二維的 DP 表格去紀錄:
* `dp[i][j]` 表示使用 `s1` 的長度 `i`，`s2` 的長度 `j`，可否組合出長度為 `i + j` 的 `s3`
* 則思考能否組合出長度 $i + j$ 的 `s3` 時，先考慮能否組合出長度 $i + j - 1$ 的 `s3`，包含 `dp[i][j - 1]` 和 `d[i - 1][j]` 兩個可能
* 如果 `dp[i][j - 1]` 為 true，考慮加入 `s2` 的第 j 個字元(`s2[j - 1]`)可否組出長度為 $i + j$ 的 `s3`?
* 如果 `dp[i - 1][j]` 為 true，考慮加入 `s1` 的第 i 個字元(`s1[i - 1]`)可否組出長度為 $i + j$ 的 `s3`?

則把此邏輯轉換成程式為:

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];
    dp[0][0] = true;

    for(int i = 1; i <= n;i++)
        dp[i][0] = dp[i - 1][0] && (s1[i - 1] == s3[i - 1]);
    
    for(int j = 1; j <= m;j++)
        dp[0][j] = dp[0][j - 1] && (s2[j - 1] == s3[j - 1]);
    

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dp[i][j] = (dp[i][j - 1] && (s2[j - 1] == s3[i + j -1])) \
                     || (dp[i - 1][j] && (s1[i - 1] == s3[i + j -1])); 
        }
    }


    return dp[n][m];
}

則在 leetcode 上的執行結果為:

`dp[j]` 表示考慮使用 j 個 `s2` 的元素時，能否和 `s1` 組成 `s3`:
* $i = 0$ 時，考慮能否只用 `s2` 的長度 $j$ 組出 `s3`，因此 `dp[j] = s2[j - 1] & s3[j - 1]`
* $i > 0$ 時
* 考慮能否用 $i$ 個 `s1` 和 $j - 1$ 個 `s2` 組成 `s3` 的 $i + j - 1$，此時 `dp[j]` 紀錄的是能否使用 $i - 1$ 個 `s1` 和 `j` 組成 `s3` 的 $i + j$ 長度，因此 `dp[j] &= (s1[i - 1] == s3[i + j - 1])`
* 考慮能否用 $i - 1$ 個 `s1` 和 $j$ 個 `s2` 組成 `s3`，因此 `dp[j] |= dp[j - 1] & (s2[j - 1] == s3[i + j - 1])`

則知道 `RRR = (b) i + j - 1`。