# 2018q1 第 1 週測驗題 --- ### 測驗 `1` 考慮以下程式碼: ```C #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` 考慮以下整數乘法的實作程式碼: ```C 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 延伸問題: * 解釋為何乘法可運作? ::: ---