# 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

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

---

### 測驗 `2`

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

:::success
延伸問題:
* 為什麼？
* 舉出類似的案例並解釋
:::

---

### 測驗 `3`

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

:::success
延伸問題:
* 在 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

:::success
延伸問題:
* 乘以某個整數的運算，如果拆解為 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;

:::success
延伸問題:
* 解釋為何乘法可運作？
:::

---