# 2019q1 第 2 週測驗題
:::info
目的: 檢驗學員對 [bitwise operator](https://hackmd.io/s/By0MltO_m) 及 C 程式設計的認知
:::

---

### 測驗 `1`

考慮以下程式碼，回傳給定整數乘上 `3.5` 的結果:

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 程式的實作:

unsigned popcnt_naive(unsigned v) {
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

可改寫為以下常數時間的實作:

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`

考慮以下程式碼:

#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 核心內部相似的程式碼
:::