# 2018q3 第 3 週測驗題 :::info 目的: 檢驗學員對 C 語言 pointer, union, bit-fields, 實作 linked list 的認知 ::: --- ### 測驗 `1` 考慮以下程式碼: ```C= #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 換為以下: ```C=10 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`: ```C 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: ```C #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` 考慮以下程式碼: ```C #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 延伸問題: 解釋運作原理，並新增刪除和搜尋節點的程式，附上完整的測試計畫 ::: ---