# 2018q1 第 2 週測驗題 --- ### 測驗 `一` ![](https://i.imgur.com/Mp0cHII.jpg) 請完成下方程式碼,依循 IEEE 754 單精度規範,輸出 $2^x$ 的浮點數表達法,而且考慮兩種狀況: * 當 $x$ 過小的時候,回傳 $0.0$ * 當 $x$ 過大的時候,回傳 $+\infty$ 注意:這裡假設 `u2f` 函式返回的浮點數值與其無號數輸入有著相同的位數,也就是至少 32-bit ```Clike #include <math.h> static inline float u2f(unsigned int x) { return *(float *) &x; } float exp2_fp(int x) { unsigned int exp /* exponent */, frac /* fraction */; /* too small */ if (x < 2 - pow(2, Y0) - 23) { exp = 0; frac = 0; /* denormalize */ } else if (x < Y1 - pow(2, Y2)) { exp = 0; frac = 1 << (unsigned) (x - (2 - pow(2, Y3) - Y4)); /* normalized */ } else if (x < pow(2, Y5)) { exp = pow(2, Y6) - 1 + x; frac = 0; /* too large */ } else { exp = Y7; frac = 0; } /* pack exp and frac into 32 bits */ return u2f((unsigned) exp << 23 | frac); } ``` ==作答區== Y0 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y1 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y2 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y3 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y4 = ? * `(a)` 20 * `(b)` 21 * `(c)` 22 * `(d)` 23 * `(e)` 24 * `(f)` 25 * `(g)` 26 * `(h)` 27 Y5 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y6 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 Y7 = ? * `(a)` 0x00 * `(b)` 0xF0 * `(c)` 0xFA * `(d)` 0xFB * `(e)` 0xFC * `(f)` 0xFD * `(g)` 0xFE * `(h)` 0xFF Reference: * [Exploration of the IEEE-754 Floating Point Standard](http://blog.ruofeidu.com/exploration-ieee-754-floating-point-standard/) [90] :::info 延伸題: 給定一個單精度的浮點數值,輸出較大且最接近的 $2^x$ 值,需要充分考慮到邊界 ::: --- ### 測驗 `二` 考慮以下程式碼對一個浮點數進行 `* 0.5` 的操作,補完程式: ```Clike typedef unsigned int float_bits; float_bits float_x0_5(float_bits f) { unsigned sig = f >> 31; unsigned rest = f & 0x7FFFFFFF; unsigned exp = f >> 23 & 0xFF; unsigned frac = f & 0x7FFFFF; /* NaN or INF */ if (exp == A0) return f; /* round to even. Last 2 bits of frac are considered: * 00 => 0 just >> 1 * 01 => 0 (round to even) just >> 1 * 10 => 1 just >> 1 * 11 => 1 + 1 (round to even) just >> 1 and plus 1 */ int addition = (frac & 0x3) == 0x3; /* Denormalized */ if (exp == 0) { frac >>= A1; frac += addition; /* Normalized to denormalized */ } else if (exp == 1) { rest >>= A2; rest += addition; exp = rest >> A3 & A4; frac = rest & 0x7FFFFF; /* Normalized */ } else { exp -= A5; } return sig << A6 | exp << 23 | frac; } ``` ==作答區== A0 = ? * `(a)` 0x00 * `(b)` 0xF0 * `(c)` 0xFA * `(d)` 0xFB * `(e)` 0xFC * `(f)` 0xFD * `(g)` 0xFE * `(h)` 0xFF A1 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 A2 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 A3 = ? * `(a)` 20 * `(b)` 21 * `(c)` 22 * `(d)` 23 * `(e)` 24 * `(f)` 25 * `(g)` 26 * `(h)` 27 A4 = ? * `(a)` 0x00 * `(b)` 0xF0 * `(c)` 0xFA * `(d)` 0xFB * `(e)` 0xFC * `(f)` 0xFD * `(g)` 0xFE * `(h)` 0xFF A5 = ? * `(a)` 0 * `(b)` 1 * `(c)` 2 * `(d)` 3 * `(e)` 4 * `(f)` 5 * `(g)` 6 * `(h)` 7 A6 = ? * `(a)` 31 * `(b)` 30 * `(c)` 29 * `(d)` 28 * `(e)` 27 * `(f)` 26 * `(g)` 25 * `(h)` 24 Reference: * [Floating Point Multiplication](https://www.doc.ic.ac.uk/~eedwards/compsys/float/) [95] --- ### 測驗 `三` 考慮到某些實數的二進位表示形式如同 $0.yyyyy...$ 這樣的無限循環小數,其中 $y$ 是個 $k$ 位的二進位序列,例如 $\frac{1}{3}$ 的二進位表示為 $0.01010101...$ (y = `01`),而 $\frac{1}{5}$ 的二進位表示為 $0.001100110011...$ (y = `0011`),考慮到以下 y 值,求出對應的十進位分數值。 * y = `010011` => $\frac{19}{X1}$ * y = `101` => $\frac{5}{X2}$ * y = `0110` => $\frac{2}{X3}$ X1 = ? * `(a)` 11 * `(b)` 23 * `(c)` 63 * `(d)` 97 * `(e)` 57 * `(f)` 31 * `(g)` 5 * `(h)` 13 X2 = ? * `(a)` 17 * `(b)` 19 * `(c)` 13 * `(d)` 11 * `(e)` 3 * `(f)` 7 * `(g)` 23 * `(h)` 97 X3 = ? * `(a)` 23 * `(b)` 19 * `(c)` 17 * `(d)` 13 * `(e)` 11 * `(f)` 7 * `(g)` 5 * `(h)` 3 Reference: * [Binary Fractions](https://www.electronics-tutorials.ws/binary/binary-fractions.html) [83] --- ### 測驗 `四` 在 [你所不知道的C語言: 遞迴呼叫篇](https://hackmd.io/s/rJ8BOjGGl) 提到以下程式碼: ```Clike #include <stdio.h> int p(int i, int N) { return (i < N && printf("%d\\n", i) &&!p(i + 1, N)) || printf("%d\\n", i); } int main() { return p(1, 10) && printf("\\n"); } ``` 預期會得到以下輸出: ``` 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> ``` 注意 `10` 只會出現一次。請填補下方程式碼,使得輸出為 `1 -> 2 -> 3 -> 4 -> 5 ->`,並且包含換行符號 (`\n`) ```Clike #include <stdio.h> int p(int i, int N) { return (i < N && printf("%d -\> ", i) && Q1(i + Q2, N + Q3)); } int main() { return p(1, 10) && printf("\\n"); } ``` 提示: Q1 是函式名稱,可能包含 `~` (bitwise NOT) 操作,Q2 和 Q3 是有號整數 ==作答區== Q1 = ? * `(a)` p * `(b)` ~p Q2 = ? * `(a)` -5 * `(b)` -4 * `(c)` -3 * `(d)` -2 * `(e)` -1 * `(f)` 0 * `(g)` 1 * `(h)` 2 * `(i)` 3 * `(j)` 4 Q3 = ? * `(a)` -5 * `(b)` -4 * `(c)` -3 * `(d)` -2 * `(e)` -1 * `(f)` 0 * `(g)` 1 * `(h)` 2 * `(i)` 3 * `(j)` 4