2018q1 Homework2 (assessment)

contributed by <rwe0214>

tags:rwe0214

課前測驗題參考作答

W1Q2

題目：

給定 B 為 2 的某次方 (power of 2)，那麼是否 A % B 會等價於 (A & (B - 1))？
(a) 是
(b) 否

延伸問題：

• 為什麼？
• 舉出類似案例並解釋

想法 ＆ 思考
從取餘數這個角度出發，一開始我先以十進位來做思考，假設我們要取某數 A 除以 power of 10 的餘數，我們很自然就會把 A 的個位數往前數幾個 B 的次方值。

e.g. 12345

${}_d$ 除以 10

${}^2$ 的餘數就是從十進制的個位開始取兩個數 45

${}_d$。

回到題目並以二進位的角度來看：

e.g. 123

${}_d$ = 1111011

${}_b$ 除以 2

${}^4$ 的餘數就是從二進制的個位開始取四個數 1011

${}_b$ = 11

${}_d$

所以我們可以確定了一件事，當取 power of 2 的餘數時，擷取被除數之次方個位數即可。接著我們來看 power of 2 的二進制表示

2

${}^3$ = 1000

${}_b$, 2

${}^3$ - 1 = 0111

${}_b$
2

${}^5$ = 100000

${}_b$, 2

${}^5$ - 1 = 011111

${}_b$

由上面可以看出 (power of 2) - 1 的值剛好在我們想要擷取的位元上都是 1，反之都是 0，如此一來便可以透過 bit mask 的手法將我們的所求位元求出，即題目所述 (A & (B - 1))！

在電腦科學裡，計算 memory 分配進哪一個 cache block 的 index 和 tag 值手法也類似於本題的求餘數。根據 cache 的關聯度 (power of 2) 去分割 memory address bits。

e.g. 一個關聯度為 4 的 cache，假設一個 set 有 4 個 blocks，且一個 block 是以四個 位元祖為單位
某一 memory address 為 m 的資料被放進 cache 時，其 index = m / (set size) / 關聯度，tag = (m / (set size)) % 關聯度。
所以 cpu 在計算上也可以直接使用 bit-operator 來求得答案。

W2Q2

題目：

完成 float / 2 的程式碼 :

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;
}

想法 ＆ 思考
首先我把程式碼分成三個部份：

1. 將 IEEE754 的各個 bits ( sign, exp, frac )皆分離出來
2. 判斷傳入的數字是否可以運算 ( NaN or INF )
3. 若可正確運算則依照數字類型 ( Denormalized, Normalized to denormalized, Normalized ) 去做除法

IEEE754 數字分類：

單精度：
          |     sign  |                exp  |         frac
----------|-----------|---------------------|---------------
+NaN      |        0  |      1111 1111(FF)  |            0
----------|-----------|---------------------|---------------
+INF      |        0  |      1111 1111(FF)  |          非零
----------|-----------|---------------------|---------------
+0        |        0  |                  0  |            0
----------|-----------|---------------------|---------------
Normal    |        X  |             1 ~ FE  |            X
----------|-----------|---------------------|---------------
Denormal  |        X  |                  0  |            X
----------|-----------|---------------------|---------------
-0        |        1  |                  0  |            0
----------|-----------|---------------------|---------------
-INF      |        1  |      1111 1111(FF)  |          非零
----------|-----------|---------------------|---------------
-NaN      |        1  |      1111 1111(FF)  |            0

基於以上規則，A1 ~ A6 的答案也呼之欲出了！
而 A1 ~ A6 之中最讓我感興趣的部份則是 A3 和 A4：

/* Normalized to denormalized */
    else if (exp == 1) {
        rest >>= 1;
        rest += addition;
        exp = rest >> 23 & 0xFF;
        frac = rest & 0x7FFFFF;
    }

如果根據註解來推論這個部份應該是除以 2 之後會是 denormalized 數，而 denormalized 的 exp 值固定為 0，既然這樣為什麼還要大費周章的使用一些運算來求得 exp 呢？
於是我假設有一種情形，一個 normalized 經過以上運算，它確實有可能變成 denormalized，但是最後的結果卻還是 normalized ，先猜測，是這個條件下的最大值。
取二個數其 IEEE754 表示法分別為
0 00000001 11111111111111111111111
和
0 00000001 11111111111111111111110
並分別紀錄 3,4,5 行並比較其執行結果為

(after rest >>= 1;)
rest = 00000000 11111111111111111111111 

(after rest += addition;)
rest = 00000001 00000000000000000000000

(after exp = rest >> 23 & 0xFF;)
exp  = 00000001

和

(after rest >>= 1;)
rest = 00000000 11111111111111111111110 

(after rest += addition;)
rest = 00000000 11111111111111111111110 

(after exp = rest >> 23 & 0xFF;)
exp  = 00000000

哦！抓到了！原來真的有特例會在最後結果仍為 normalized！
所以為了為了保持其正確性才把這部份使用運算來計算而不是直接 assign 為 0。

W2Q3

題目：

#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 -
填補以下程式碼使得輸出為
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"); }

想法 ＆ 思考
這題當初在測驗的時候因為前面幾題花費較多時間，所以最後沒有時間作答。

不過這題的題目乍看之下很複雜，但是把遞迴展開一些後，便能豁然開朗。
以要填補的程式碼為例，展開幾項後：

return p(1, 10) && printf("\\n");
          |
          |
          V
1<10 && printf("1 ->") && Q1(1+1, 10-1)
                              |
                              |
                              V
                   2<9 && printf("2 ->") && Q1(2+1, 9-1)
                                                |
                                                :
                                                :
                                           ( 過程省略 )
                                                :
                                                :
                                                |
                                                V
                                       5<6 && printf("5 ->") && Q1(5+1, 6-1)
                                                                  |
                                                                  |
                                                                  V
                                                             6<5 ,return false

由以上過程可得知若要包含最後的換行符號 ( \n )，則 p(1,10) 必須回傳 true，所以 Q1 為 ~p！

因為自動飲料機而延畢的那一年讀後心得