# 2019q1 第 2 週測驗題 :::info 目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m) 及 C 程式設計的認知 ::: --- ### 測驗 `1` 考慮以下程式碼，回傳給定整數乘上 `3.5` 的結果: ```clike int mul3_5(int x) { return (((8 A x) B x ) C 1); } ``` 請補完。A, B, C 都是 operator。 ==作答區== A = ? * `(a)` + * `(b)` - * `(c)` * * `(d)` / * `(e)` << * `(f)` >> * `(g)` | * `(h)` & * `(i)` ^ B = ? * `(a)` + * `(b)` - * `(c)` * * `(d)` / * `(e)` << * `(f)` >> * `(g)` | * `(h)` & * `(i)` ^ C = ? * `(a)` + * `(b)` - * `(c)` * * `(d)` / * `(e)` << * `(f)` >> * `(g)` | * `(h)` & * `(i)` ^ :::success 延伸題目: 1. 早期的 C 語言做數值運算時，會將 `int` 轉型為 `double` (`float` 型態是 ANSI 標準化時才納入)，待運算完畢後，再轉型回 `int`。本例來說，原本 `* 3.5` 的操作就意味著要先將 `int` 轉型為 `float`/`double` 並在運算後再去轉型，涉及較多的指令週期，但適當調整後，則可避免轉型到浮點數再轉回的成本。研讀相關文獻，找出類似的最佳化技巧; 2. 編譯器將原始程式碼解析為 abstract syntax tree (AST) 後，是如何處理上述語意分析呢？請用 gcc/clang 舉例說明; ::: --- ### 測驗 `2` [population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 `1`，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 `0` 元素個數、計算兩個字串的 [Hamming distance](https://en.wikipedia.org/wiki/Hamming_weight)。Intel 在 2008 年 11 月 Nehalem 架構的處理器 Core i7 引入 SSE4.2 指令集，其中就有 `CRC32` 和 `POPCNT` 指令，`POPCNT` 可處理 16-bit, 32-bit, 64-bit 整數。 對應到 C 程式的實作: ```clike unsigned popcnt_naive(unsigned v) { unsigned n = 0; while (v) v &= (v - 1), n = -(~n); return n; } ``` 可改寫為以下常數時間的實作: ```clike unsigned popcnt(unsigned v) { unsigned n; n = (v >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; n = (n >> 1) & 0x77777777; v -= n; v = (v + (v >> X)) & Y; v *= 0x01010101; return v >> 24; } ``` 請補完。 ==作答區== X = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y = ? * `(a)` 0x55555555 * `(b)` 0x33333333 * `(c)` 0x0F0F0F0F * `(d)` 0x00FF00FF * `(e)` 0x0000FFFF * `(f)` 0x0F0F0F0F :::success 延伸題目: 解釋原理並找出可抵抗 [timing attack](https://en.wikipedia.org/wiki/Timing_attack) 的相關程式和場景 ::: --- ### 測驗 `3` 考慮以下程式碼: ```clike #include <stdio.h> #define cons(x, y) E struct llist { int val; struct llist *next; }; int main() { struct llist *list = cons(9, cons(5, cons(4, cons(7, NULL)))); struct llist *p = list; for (; p; p = p->next) printf("%d", p->val); printf("\n"); return 0; } ``` 預期執行時期輸出 `9547`，補完 `E`。 E = ? * `(a)` {x, y} * `(b)` {{x, y}} * `(c)` {.val = x, .next = y} * `(d)` (struct llist[]){.val = x, .next = y} * `(e)` (struct llist[]){{x, y}} :::success 延伸題目: 參照 C 語言規格，解釋原理並找出 Linux 核心內部相似的程式碼 :::