# 2018q3 第 1 週測驗題 :::info 目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m) 的認知 ::: --- ### 測驗 `1` 考慮以下程式碼: ```C int my_xor(int x, int y) { return (x | y) OP1 (OP2 x OP3 OP4 y); } int main() { int x = 3, y = 5; return my_xor(x, y); } ``` `my_xor` 嘗試不用 XOR 運算子做出等效的 XOR 運算,其中 OP1, OP2, OP3, OP4 都是 operator,請補完實作。 ==作答區== OP1 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP2 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP3 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * OP4 = ? * `(a)` | * `(b)` & * `(c)` ~ * `(d)` % * `(e)` * --- ### 測驗 `2` parity (check) bit 可翻譯為「奇偶校驗位元」或「同位檢查位元」,常見於降低資料傳輸的錯誤。在資料傳送出去前,先在資料原有位元額外加上一個 parity bit,再將 parity bit 與資料的位元所組成的位元傳送出去,待接收完畢後,就檢查看看是否有奇數個 `1` 或偶數個 `1`,以判斷有無發生錯誤。 parity bit 有兩種類型: * 偶校驗位 (even): `1` 的個數加起來須為偶數個 * 奇校驗位 (odd): `1` 的個數加起來須為奇數個 範例 1: * 輸入: 254 * 輸出: odd parity * 解釋 * 254~10~ 的二進位表示為 `11111110`,其中共有 7 個 `1`,奇數個 範例 2: * 輸入: 1742346774 * 輸出: even parity 同位元檢查已經廣泛地應用到電腦的主記憶體,其優點是只要利用 XOR 或 NOT,就能製造成硬體;缺點則是無法更正錯誤,也無法偵測到所有錯誤,一旦接收到的位元圖樣同時有偶數個 (2, 4, 6, ...個) 位元錯誤,就偵測不到錯誤,因為在這種情況下,`1` 的個數仍舊會維持奇數個或偶數個。 考慮到以下判斷 parity bit 的程式碼 ```cpp #include <stdio.h> /* Generate look-up table while pre-processing */ #define P2(n) n, n ^ 1, n ^ 1, n #define P4(n) P2(n), P2(n ^ 1), P2(n ^ 1), P2(n) #define P6(n) P4(n), P4(n ^ 1), P4(n ^ 1), P4(n) #define LOOK_UP P6(0), P6(1), P6(1), P6(0) /* LOOK_UP is the macro expansion to generate table */ unsigned int table[256] = { LOOK_UP }; int parity(int num) { /* Number is considered to be of 32 bits */ int max = 16; // Dividing the number into 8-bit // chunks while performing XOR while (max >= 8) { num = num ^ (num >> max); max /= N; } // Masking the number with 0xff (11111111) // to produce valid 8-bit result return table[num & 0xff]; } int main() { unsigned int num = 1742346774; /* Result is 1 for odd parity, 0 for even parity */ int result = parity(num); printf("%s parity\n", parity(num) ? "odd" : "even"); return 0; } ``` 補完程式碼。 ==作答區== N = ? * `(a)` 8 * `(b)` 7 * `(c)` 6 * `(d)` 5 * `(e)` 4 * `(f)` 3 * `(g)` 2 * `(h)` 1 :::warning 延伸題目: 解釋和實作循環冗餘碼 (CRC) 程式碼 :::