2019q1 第 2 週測驗題

目的: 檢驗學員對 bitwise operator 及 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) ^

延伸題目:

早期的 C 語言做數值運算時，會將 int 轉型為 double (float 型態是 ANSI 標準化時才納入)，待運算完畢後，再轉型回 int。本例來說，原本 * 3.5 的操作就意味著要先將 int 轉型為 float/double 並在運算後再去轉型，涉及較多的指令週期，但適當調整後，則可避免轉型到浮點數再轉回的成本。研讀相關文獻，找出類似的最佳化技巧;
編譯器將原始程式碼解析為 abstract syntax tree (AST) 後，是如何處理上述語意分析呢？請用 gcc/clang 舉例說明;

測驗 `2`

population count 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1，在一些場合下很有用，例如計算 0-1 稀疏矩陣 (sparse matrix)或 bit array 中非 0 元素個數、計算兩個字串的 Hamming distance。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

延伸題目: 解釋原理並找出可抵抗 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}}

延伸題目: 參照 C 語言規格，解釋原理並找出 Linux 核心內部相似的程式碼

2019q1 第 2 週測驗題

測驗 1

測驗 2

測驗 3

測驗 `1`

測驗 `2`

測驗 `3`