2020q3 第 7 週測驗題

tags: sysprog2020

目的: 檢驗學員對 bitwise 操作, 遞迴呼叫, 編譯器最佳化 的認知

作答表單

測驗 1

給定兩個函式實作:

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 的觀點，請從下列選項挑出正確的陳述。

作答區

T = ?

• (a) funcA 和 funcB 都屬於 Tail recursion，適用編譯器的 tail call optimization (TCO)
• (b) funcA 是 Tail recursion，但 funcB 不是 Tail recursion
• (c) funcB 是 Tail recursion，但 funcA 不是 Tail recursion
• (d) funcA 和 funcB 兩者都不是 Tail recursion

延伸問題:

• 設計實驗，解釋 clang/gcc 在最佳化 (-O2 以上) 開啟時，上述程式碼的行為，以及 tail call optimization (TCO) 適用場景為何

---

測驗 2

考慮測試 C 編譯器 Tail Call Optimization (TCO) 能力的程式 tco-test，在 gcc-8.4.0 中抑制最佳化 (也就是 -O0 編譯選項) 進行編譯，得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O0 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                no TCO
One argument:                                no TCO
Additional int argument:                     no TCO
Dropped int argument:                        no TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          no TCO

而在開啟最佳化 (這裡用 -O2 等級) 編譯，會得到以下執行結果:

$ gcc -Wall -Wextra -Wno-unused-parameter -O2 main.c first.c second.c -o chaining
$ ./chaining
No arguments:                                TCO
One argument:                                TCO
Additional int argument:                     TCO
Dropped int argument:                        TCO
char return to int:                          no TCO
int return to char:                          no TCO
int return to void:                          TCO

注意 __builtin_return_address 是 gcc 的內建函式:

This function returns the return address of the current function, or of one of its callers. The level argument is number of frames to scan up the call stack. A value of 0 yields the return address of the current function, a value of 1 yields the return address of the caller of the current function, and so forth. When inlining the expected behavior is that the function returns the address of the function that is returned to. To work around this behavior use the noinline function attribute.
The level argument must be a constant integer.

從實驗中可發現下方程式無法對 g 函式施加 TCO:

void g(int *p);
void f(void) {
    int x = 3;
    g(&x);
}
void g(int *p) { printf("%d\n", *p); }

因為函式 f 的區域變數 x 在返回後就不再存在於 stack。考慮以下程式碼:

int *global_var;
void f(void)
{
    int x = 3;
    global_var = &x;
    ...
    /* Can the compiler perform TCO here? */
    g();
}

思考程式註解，在第 8 行能否施加 TCO 呢？選出最適合的解釋。

作答區

Q = ?

• (a) 編譯器不可能施加 TCO
• (b) 編譯器一定可施加 TCO
• (c) 只要函式 g 沒有對 global_var 指標作 dereference，那麼 TCO 就有機會

延伸問題:

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

---

測驗 3

軟體開發者 Max Howell 在 Twitter 講述他在 2015 年是怎麼在 Google 面試時被刷掉： (出處)

「Google：我們 90% 的工程師都用你寫的軟體（Homebrew），但你沒辦法在白板上實作 Invert Binary Tree，所以因此我們決定不聘用你」

摘自 iOS 神人應徵工作之滑鐵盧事件:

• 我們會希望透過高互動的面談程序，來進一步確認被面談者是否是符合開發團隊需求的人。
• 懂得演算法和資料結構的運用，當然是程式設計者的基本必備條件，但是，被面談者或許記不住一些資料結構或演算法的細節，如果面談的重點放在細節必須完全無誤，而這些細節是翻書或網上就隨時可以查到的，那麼，因為被面談者無法正確回答出這些細節，就刷掉一個有潛力的程式設計者，其實是很可惜的一件事。

LeetCode 226. Invert Binary Tree 本質上就是找出二元樹的鏡像 (mirror):

以下是參考實作:

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;
}

若將上述程式碼的第 12 行和第 13 行對調，是否會影響最終輸出？

作答區
P = ?

• (a) 會影響，程式執行將會錯誤
• (b) 不影響，依然可產生符合預期的輸出

延伸問題:

1. 解釋上述程式運作原理，並探討編譯器針對遞迴呼叫的最佳化空間;
2. 用 iteration 改寫，並降低記憶體開銷，需要用 Valgrind 一類的分析工具驗證;

---

測驗 4

LeetCoee 201. Bitwise AND of Numbers Range 給一個範圍

$[m,n]$ 且

$0\le m\le n\le 2147483647$，回傳對所有該範圍的數值進行位元運算 AND 的結果，範圍包含邊界。

解題思路

以

$m=100$ (0110 0100₂),

$n=120$ (0111 1000₂) 來說，

$m\wedge n$ 是 96 (0110 0000₂)，而

$n-m=20$，於是我們可設計一個 bit mask 來求解，使低 5 個位元皆為 0。

以下是一個對應的解法：

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 = ?

• (a) ~((1U << count) - 1)
• (b) ~(1U << count)
• (c) (~1U - count)
• (d) ~((1U << count) + 1)
• (e) (~1U ^ count)
• (f) (~1U ^ (1 << count))
• (g) (~1U ^ (1 << count) - 1)

延伸問題:

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

---

測驗 5

LeetCode 97. Interleaving String:

大意是判斷給定的字串 s1 與 s2 可否交錯形成字串 s3。從上圖可見，走訪 s3 所有字元，其字元必定是來自 s1 或來自 s2，並且 s1 與 s2 的字元也是依序取出，也就是 s3[i3] 必定為 s1[i1] 或 s2[i2]，其中 i1, i2, i3 分別為 s1, s2, s3 目前的位置。

解題思路

考慮一項 Dynamic Programming (動態規劃) 的實作如下:

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;
            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];
}

請補完程式碼，使其符合 LeetCode 題目規範。

sizeof(bool) is implementation-defined. 不必然為 1

延伸閱讀:

• Competitive Programmer’s Handbook - Dynamic Programming 重點提示 / 電子書

作答區

RRR = ?

• (a) i + j
• (b) i + j - 1
• (c) j - 1

延伸問題:

1. 解釋上述程式運作原理，並探討改進的方式
2. Dynamic Programming 技巧需要額外的記憶體空間，請針對上述程式，提出降低記憶體開銷的手段

---