2018q1 第 1 週測驗題

---

測驗 1

考慮以下程式碼:

#include <stdlib.h>
int isMultN(unsigned int n) {
    int odd_c = 0, even_c = 0; /* variables to count odd and even SET bits */
    
    if (n == 0)    // return true if difference is 0.
        return 1;
    if (n == 1)    // return false if the difference is not 0.
        return 0;
    
    while (n) {
        if (n & 1)   // odd bit is SET, increment odd_C
            odd_c++;
        n >>= 1; 
    
        if (n & 1)   // even bit is SET, increment even_c
            even_c++;
        n = n >> 1;
    }
    
    /* Recursive call till you get 0/1 */
    return(isMultN(abs(odd_c - even_c)));
}

其作用為檢查輸入整數是否為 N 的倍數，那麼 N 為多少？
(a) 13
(b) 11
(c) 7
(b) 5
(e) 3
(f) 2

延伸問題:

• 為什麼上述程式碼可運作呢？
• 將 N 改為其他質數再改寫為對應的程式碼，一樣使用遞迴

---

測驗 2

給定 B 為 2 的某次方 (power of 2)，那麼是否 A % B 等價於 (A & (B - 1))?
(a) 是
(b) 否

延伸問題:

• 為什麼？
• 舉出類似的案例並解釋

---

測驗 3

在 C 程式中，表達式 1 << 2 + 3 << 4 求值後為何？
(a) 512
(b) 16
(c) 26
(d) 52
(e) 25

延伸問題:

• 在 C 語言規格書中，找出對應運算子優先權的描述並嘗試解讀

---

測驗 4

考慮某些硬體平台執行乘法的時間較長，我們會以 (x << 5) - (x) 取代 * 31，那麼 * (-6) 該如何用 shift 搭配 add/sub 實作呢？
(a) 2 個 shift 搭配 0 個 add/sub
(b) 2 個 shift 搭配 2 個 add/sub
(c) 2 個 shift 搭配 1 個 add/sub
(d) 1 個 shift 搭配 1 個 add/sub
(e) 0 個 shift 搭配 2 個 add/sub

延伸問題:

• 乘以某個整數的運算，如果拆解為 shift 和 add/sub 的組合，是否存在最小值的唯一解？

---

測驗 5

考慮以下整數乘法的實作程式碼:

int mul(int n, int m) { 
    int ret = 0;
    for (int c = 0; m; c++, m /= 2)
        if (!(m % 2 - 1)) OP
    return ret;
}

上述 OP 對應到下方哪個程式敘述呢？
(a) ret = n << c;
(b) ret += n;
(c) ret <<= n;
(d) ret = c << n;
(e) ret += n << c;

延伸問題:

• 解釋為何乘法可運作？

---