# 2018q3 第 17 週測驗題 (上)

### 測驗 `1`

考慮以下 C 程式:

int x = 2;
int main() {
    int x = 1;
    {
        extern int x;
        return x;
    }
}

執行後程式返回值 (program exit code, 用 `echo $?` 可得知) 為何？

==作答區==

* `(a)` 2
* `(b)` 1
* `(c)` 0
* `(d)` 沒定義

:::success
延伸問題: 查閱相關 C 語言規格解釋，並探討對應的資訊安全問題
:::

---

### 測驗 `2`

考慮以下 C 程式:

typedef struct { char *key; char *value; } T1;
typedef struct { long type; char *value; } T2;
T1 a[] = {
    [1] = {
        "", ((char *) &((T2) {2, (char *) 3})),
    }
};
int main() {                             
    T2 *p = (T2 *) a[1].value;
    return (int) p->value;
}

執行後程式返回值為何？

==作答區==

* `(a)` 1
* `(b)` 2
* `(c)` 3
* `(d)` 標準沒有定義

:::success
延伸問題: 查閱相關 C 語言規格解釋，並探討對應的資訊安全問題
:::

---

### 測驗 `3`

考慮以下程式碼，預期的 UNIX 終端機輸出為何？

#include <stdio.h>
unsigned long foo() {
    return (unsigned long) - 1 / 8;       
}
int main() {
    printf("%d\n", (signed) foo());
}

==作答區==

* `(a)` 1
* `(b)` 0
* `(c)` -1
* `(d)` 標準沒有定義

:::success
延伸問題: 從 C 編譯器的角度，解釋為何如此
:::

---

### 測驗 `4`

考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    while (v) {                               
        uint64_t t = v;
        v = u % v;
        u = t;
    }
    return u;
}

改寫為以下等價實作:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {
    if (!u || !v) return u | v;
    int shift;
    for (shift = 0; !((u | v) & 1); shift++) {
        u /= 2, v /= 2;
    }
    while (!(u & 1))
        u /= 2;
    do {
        while (!(v & 1))
            v /= 2;
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v;
            v = t;
        }
    } while (K1);
    return K2;
}

補完以上程式碼。

==作答區==

K1 = ?
* `(a)` u
* `(b)` v
* `(c)` u - v
* `(d)` v - u
* `(e)` u & 1
* `(f)` v & 1

K2 = ?
* `(a)` u
* `(b)` v
* `(c)` u - v
* `(d)` v - u
* `(e)` u >> shift
* `(f)` v >> shift
* `(g)` u << shift
* `(h)` v << shift

---

### 測驗 `5`

承測驗 `4`, 透過 gcc 內建的 [\_\_builtin_ctz](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) (Returns the number of trailing 0-bits in x, starting at the least significant bit position) 改寫程式碼如下:

#include <stdint.h>
uint64_t gcd(uint64_t u, uint64_t v) {   
    if (!u || !v) return u | v;
    int shift = __builtin_ctzll(Z1);
    u >>= __builtin_ctzll(u);
    while (v) {
        v >>= __builtin_ctzll(v);
        if (u < v) {
            v -= u;
        } else {
            uint64_t t = u - v;
            u = v, v = t;
        }
    }
    return Z2;         
}

補完以上程式碼。

==作答區==

Z1 = ?
* `(a)` u
* `(b)` v
* `(c)` u & v
* `(d)` v | u
* `(e)` u & 1
* `(f)` v & 1

Z2 = ?
* `(a)` u
* `(b)` v
* `(c)` u - v
* `(d)` v - u
* `(e)` u >> shift
* `(f)` v >> shift
* `(g)` u << shift
* `(h)` v << shift

:::success
延伸問題: 解釋上述程式程式運作原理，以及在 x86_64 上透過 [\_\_builtin_ctz](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫 GCD 對效能的提升
:::