# 2018q3 第 1 週測驗題
:::info
目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m) 的認知
:::

---

### 測驗 `1`

考慮以下程式碼:

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 的程式碼

#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) 程式碼
:::