# 2020 年秋季「進階電腦系統理論與實作」課程專題 (quiz7)
contributed by < `erickuo5124` >
###### tags: `2020進階電腦系統理論與實作`
> [題目描述](https://hackmd.io/@sysprog/2020-quiz7)

### 測驗`1`
#### T = ?
`(c)`僅 funcB 是 Tail recursion

> Tail Call
> In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail-recursive, which is a special case of direct recursion.

funcA 的回傳值除了 funcA 本身之外還要另外做 *5 ，因此不是 Tail recursion

#### 實驗

---

### 測驗`2`
#### Q = ?
`(b)`編譯器一定可施加 TCO

函式 `f` 的區域變數 `x` 在返回後就不再存在於 stack，但全域變數 `global_var` 在程式執行時會一值存在，並指向原先 `x` 的位置，因此可以施加 TCO

#### 探討 TCO 和遞迴程式的原理
#### 分析上述實驗的行為和解釋 gcc 對 TCO 的操作
#### 從 GitHub 裡頭找出 __builtin_return_address 的應用案例並解說

---

### 測驗`3`
#### P = ?
`(b)` 不影響，依然可產生符合預期的輸出

僅僅是左右哪邊先處理，不影響最後結果。
#### 解釋上述程式運作原理，並探討編譯器針對遞迴呼叫的最佳化空間
#### 用 iteration 改寫，並降低記憶體開銷，需要用 Valgrind 一類的分析工具驗證

struct TreeNode *invertTree_iteration(struct TreeNode *root)
{ 
    if (!root)
        return NULL;

    if (!root->left && !root->right)
        return root;

    struct TreeNode *curr = root;
    struct TreeNode *tmp;
    while(1){
        tmp = curr->left;
        curr->left = curr->right;
        curr->right = tmp;
        
        if(curr->left) curr = curr->left;
        else if(curr->right) curr = curr->right;
        else if(curr->parent) curr = curr->parent;
        else break;
    }
    
    return root;
}

---

### 測驗`4`
#### MASK = ？
`(a)` `~((1U << count) - 1)`

[解題思路](https://hackmd.io/@Zero871015/LeetCode-201)給了我們一個想法：

> 將頭尾取出，並將兩數從左至右一個 bit 一個 bit 比對，直到出現一個「不一樣的 bit」，把包含那個 bit 後面補 0 並輸出。

在題目中：
- `m & n` 可以得到在那個「不一樣的 bit」之前的正確答案
- `MASK` 需要將包含那個「不一樣的 bit」之後的 bit 全部變成 0
- `diff` 兩數的差，可以透過 `__builtin_clz` 得到那個「不一樣的 bit」的位置
- `count` 得到要變 0 的個數

將 1 往左移 `count` 的數量後減 1 即可得到要變 0 的地方(但這時會是 1)，對它做 NOT 即可得到 `MASK`

#### 解釋上述程式運作原理，並探討改進的方式
#### 能否實作完全無分支 (branchless) 且滿足上述 LeetCode 要求的程式碼？請探討並實作

// runtime error: passing zero to clz(), which is not a valid argument
int rangeBitwiseAnd(int m, int n)
{ 
    int diff = n - m;
    int count = 32U - __builtin_clz(diff);
    return m & n & MASK;
}

---

### 測驗`5`
#### RRR = ？
`(b)` `i + j - 1`
[解題思路](https://medium.com/@bill800227/leetcode-97-interleaving-string-18b1202fb0ea)中提到
> s1[i-1] == s3[i+j-1] : 這個代表我們可以取出s1當前的元素來形成s3的下一個元素，所以這時候我們的transfer formula就會變成:
dp[i][j] = dp[i-1][j] && (s1[i-1] ==s3[i+j-1])

可得知 `p` = `i + j - 1`