# 2018q3 第 3 週測驗題
:::info
目的: 檢驗學員對 C 語言 pointer, union, bit-fields, 實作 linked list 的認知
:::

---

### 測驗 `1`

考慮以下程式碼:

#include <stdio.h>
#include <stdint.h>
struct test {
    unsigned int x : 5;
    unsigned int y : 5;
    unsigned int z;
};
int main() {
    struct test t;
    printf("Offset of z in struct test is %ld\n",
           (uintptr_t) &t.z - (uintptr_t) &t);
    return 0;
}

在 GNU/Linux x86_64 環境中執行，得到以下輸出:

Offset of z in struct test is 4

倘若將第 10 和第 11 換為以下:

    printf("Address of t.x is %p", &t.x);

會發生什麼事？

==作答區==

* `(a)` 印出類似 `0x7ffd144e8ad4` 的輸出，也就是 `t` 結構物件的位址;
* `(b)` 印出類似 `0x7ffd144e8ad4` 的輸出，和 `t` 結構物件差距 4 bytes;
* `(c)` 可以印出數值，但這與編譯器實作有關，不能解讀;
* `(d)` 編譯失敗，不能這樣宣告結構體的成員;
* `(e)` 編譯失敗，不能將指標指向沒有對齊 1 byte 的結構體成員;

參考資料: [Portable Bit Fields in packetC](https://link.springer.com/content/pdf/10.1007/978-1-4302-4159-1_34.pdf)

:::success
延伸問題: 解釋原因，並且找出 C99/C11 規格書對應的描述
:::

---

### 測驗 `2`

考慮以下程式碼，在 little-endian 硬體上，會返回 `1`，反之，在 big-endian 硬體上會返回 `0`:

int main() {
    union { int a; char b;
    } c = { .a = K1 };
    return c.b == K2;
}

補完上述程式碼。

==作答區==

K1 = ?
* `(a)` 0
* `(b)` 1
* `(c)` -1
* `(d)` 254

K2 = ?
* `(a)` 0
* `(b)` 1
* `(c)` 254

:::success
延伸問題: 解釋運作原理，並找出類似的程式碼
:::

---

### 測驗 `3`

以下程式碼計算 parity bit:

#include <stdint.h>
int parity(uint32_t x)
    x ^= x >> 1;
    x ^= x >> 2;
    x = (x & 0x11111111U) * 0x11111111U;
    return (x >> P) & 1;
}

補完程式碼

==作答區==

P = ?
* `(a)` 32
* `(b)` 31
* `(c)` 30
* `(d)` 29
* `(e)` 28
* `(f)` 27
* `(g)` 26
* `(h)` 25
* `(i)` 24

:::success
延伸問題: 解釋原理，並且提出更快的實作機制 (提示: 透過 SIMD)
:::

---

### 測驗 `4`

考慮以下程式碼:

#include <stdlib.h>
#include <string.h>

typedef struct rec {
    char *value;
    struct rec *next;
} record;

void insert_sorted(record **r, const char *value)
{
    record *newrec = NULL;
    while (*r && strcmp(value, (*r)->value) > 0)
        r = &((F1)->next);
    newrec = malloc(sizeof(record));
    newrec->value = F2(value);
    newrec->next = F3;
    F4 = newrec;                                                                                                                                             
}

函式 `insert_sorted` 的作用是在 r 所指向已依據數值排序的 linked list 中，安插給定的字串，考慮到 string literal 的生命週期，應該在新建立的節點中，複製給定的字串。

請補完上述程式碼。

==作答區==

F1 = ?
* `(a)` r
* `(b)` **r
* `(c)` *r
* `(d)` r->next
* `(e)` *r->next

F2 = ?
* `(a)` 無
* `(b)` strdup
* `(c)` strcpy
* `(d)` strlen
* `(e)` strcmp

F3 = ?
* `(a)` r
* `(b)` **r
* `(c)` *r
* `(d)` r->next
* `(e)` *r->next

F4 = ?
* `(a)` **r
* `(b)` *r
* `(c)` r
* `(d)` r->next
* `(e)` *r->next

:::success
延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫
:::

---