HackMD2018q3 第 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)沒定義
延伸問題: 查閱相關 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)標準沒有定義
延伸問題: 查閱相關 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)標準沒有定義
延伸問題: 從 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 (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
延伸問題: 解釋上述程式程式運作原理，以及在 x86_64 上透過 __builtin_ctz 改寫 GCD 對效能的提升
