# 2018q1 第 2 週測驗題

---

### 測驗 `一`


請完成下方程式碼，依循 IEEE 754 單精度規範，輸出 $2^x$ 的浮點數表達法，而且考慮兩種狀況：
* 當 $x$ 過小的時候，回傳 $0.0$
* 當 $x$ 過大的時候，回傳 $+\infty$

注意：這裡假設 `u2f` 函式返回的浮點數值與其無號數輸入有著相同的位數，也就是至少 32-bit

#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` 的操作，補完程式:

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) 提到以下程式碼:

#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`)

#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