# 2020q3 Homework6 (quiz6)
contributed by < `sammer1107` >

###### tags: `進階電腦系統理論與實作`

==[測驗題目](https://hackmd.io/@sysprog/2020-quiz6)==

# 測驗 1

float fp32tobf16(float x) {
    float y = x;
    int *py = (int *) &y;
    unsigned int exp, man;
    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;
    if (!exp && !man) /* zero */           
        return x;
    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

    /* Normalized number. round to nearest */
    float r = x;
    int *pr = (int *) &r;
    *pr &= 0xff800000;
    r /= 256;
    y = x + r;

    *py &= 0xffff0000;
    return y;
}

+ ==3==: 在 c 語言中，其實是不能夠對 floating point 作bitwise 運算的。所以我們必須先把他強制轉型成 int 。才能直接對浮點數作位元操作。
+ ==5~10==： 這裡我們分別把 exponent 與 mantissa 取出來，來判斷是不是特別的情況
+ 如果都為0，那麼數值肯定是 $\pm 0$，這種情況下最低的 16 位已經沒用到，所以可以直結回傳。
+ 如果 exp 為全 1，則為 infinity(`man == 0`) 或 NaN(`man != 0`)。infinity 的話也可以直接回傳。**但 NaN 的部份應該更加小心，因為 mantissa 只要不為 0 就算 NaN**
+ 如果要縮成 16 bit，應該也要做 `& 0xffff0000` 來去除低位的 bit 才對。
+ 但得要確保 bfloat16 的 mantissa 範圍內仍有 1 才行，否則單純去除低位 bit 有可能會讓 NaN 變成 bfloat16 的 infinity
故這部份應該改成：

        if (exp == 0x7F800000u) {  /* infinity or NaN */
            // make sure the mantissa is non-zero if NaN
            *py |= ((man != 0) << 16);
            *py &= 0xFFFF0000;
            return y;
        }

+ ==12~17==: 這一部份要剩下 normalized 與 denormalized number 要處理
+ 做完 15 行後相當於把原本 `x` 的 mantissa 歸 0 變成 `r`。e.g. $x = 2^{23} \cdot 1.10011011... \to r=2^{23} \cdot 1.00000000...$
+ 再來除以 $256 = 2^8$ 次方的動作是為了作 rounding，如果原本 mantissa 中的第 16 bit 為 1 (對應 `0x000080000` 這個位置，也就是 bfloat16 範圍外的第一個 bit)，加上 `r` 之後就會進位。**要注意這裡 `r` 是浮點數型態，所以除以 `256` 不是單純向右移，而是把 exponent 減 8 。** e.g.
\begin{align}
r/256 &= 2^{23-8} = 2^{15}\\
x+r/256 &= 2^{23} \cdot (1.10011011 + 0.00000001)\\
&= 2^{23} \cdot 1.10011100
\end{align}
如此完成進位。
+ denormalized 所獲得的 r 為 0，所以不會變化，相當於直接 truncate。
+ ==19~20==： 這裡再把低位的 16 個 bit 去掉就行了。
# 測驗 2

#define NEXT_START_INDEX(BUF) \
    (((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)

+ 此 ring buffer 的實作是利用一個大小 size+1 的 array。當 ring buffer 為空時，end 與 start 指向同一個地方。每當放入新元素，就是放在 end 的位置，然後移動 end 到下一個位置。讀取的時候則是從 start 讀取，然後移動 start ㄉ當滿了的時候則是 end 在 start前一個位置，這時 end 沒放東西，所以最大只能放 size 個元素。
+ `NEXT_START_INDEX` 的功用在於找到 `start` 的下一個位置，這其實就是 `start+1`，除了當 `start`在最後一格時，要繞回來 0 。`NEXT_END_INDEX` 同理。所以兩個答案都為 1。

## do {...} while(0)
+ 當我們要寫一個由多個 statement 構成的 macro function 時，我們可以利用 `do {...} while(0)` 來把這些 statement 包起來，來讓整個東西變成一個 regular statement。
+ 在 c 的標準中， **do ==statement== while (==expression==);** 放在 **iteration statement** 的定義當中，這個東西特別的地方他可以夾帶一個 compound statement (`{...}`)而且他是以 **`;`** 作為結尾，這讓他跟 **expression statement** 很類似，而一般的函式呼叫就是屬於 expression statement。
+ c 的標準中似乎沒有 regular statement 的定義，但我想 [stackoverflow 的回答](https://stackoverflow.com/questions/1067226/c-multi-line-macro-do-while0-vs-scope-block) 是要表達上述的意思。
:::warning
TODO: 用 dangling else 的處置來回覆本題
:notes: jserv
:::

# 測驗 3
這題為一個 singly-linked list 加上對應的 insertion sort 的實作。

+ 先看 `llist` 與 `cons(x,y)` 的定義：

    #define cons(x, y) (struct llist[]){{y, x}}
            
    struct llist {
        int val;
        struct llist *next;
    };

首先這題用到 compound literal 的技巧，根據 c standard:

> A postfix expression that consists of a parenthesized type name followed by a brace-
enclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.

也就是長這樣的東西：==( **type-name** ) { **initializer-list** }==
+ 在這裡 **type-name** 就是 `struct llist[]`，**initializer-list** 就是 `{y,x}`，用來初始化這個 array of struct llist 的第0個元素(其中 `y` 用來初始化 `val`，`x` 初始化 `next` )，而整個 array 也就只有一個元素。
+ 整個 `cons(x,y)` 會成為一個 lvalue，array 會被轉成 pointer，可以再被傳入下一層 `cons` 作為初始值。
+ 弄懂這個原理後，其實也可以把他寫成這樣。雖然比較醜，但是可以確認我對這東西的理解是正確的：

        #define cons(x, y) (struct llist*){&(struct llist){y, x}}

我們利用 `(struct llist){y, x}` 來創造一個 `struct llist`，對他取址，再用這個地址初始化一個 `struct llist*`。如此同樣可以達成一樣的效果。
+ ==void sort(struct llist **head)==

    void sort(struct llist **head)
    {
        struct llist *sorted = NULL;
        for (struct llist *current = *head; current;) {
            struct llist *next = current->next;
            sorted_insert(&sorted, current);
            current = next;
        }
        *head = sorted;
    }

這裡為 insertion sort 的主體，迴圈做的事就是逐點走訪 linked list，把每個節點利用 `sorted_insert()` 來把這個節點加到已排序好的 list。
+ ==void sorted_insert(struct llist **head, struct llist *node)==

    void sorted_insert(struct llist **head, struct llist *node)
    {
        if (!*head || (*head)->val >= node->val) {
            node->next = *head;
            *head = node;	
            return;
        }
        struct llist *current = *head;
        while (current->next && current->next->val < node->val)
            current = current->next;
        node->next = current->next;
        current->next = node;
    }

+ 第 ==3== 行檢查新的節點是不是最小的，如果是就把頭換成新的節點。所以答案如上。
+ ==8~12==：如果不是，就逐漸走訪排序好的 list，直到走到合適的地方再插入。

# 測驗 4
## 原理
+ 這題的原理與之前 [quiz2-測驗6](https://hackmd.io/@sammer1107/ryHs1sESP) 的概念有點類似。一樣都是分開數每個 bit 出現的次數。
+ 陣列有 $n$ 個數值，數值的範圍是 $1,2,\ldots,n−1$，只有 $n-1$ 種，所以根據鴿籠原理一定會有至少一個數字重複，而根據題目，只會有一個數字重複，且出現次數不定。
+ 我們先看一個例子。假設 $n=5$，且每個數字都會出現，也就是重複的數字只會出現兩次的情況。
| 數字 | binary |
|:-------------------:|:------:|
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 各位置 1 出現的次數 | 122 |
+ 現在如果我們選擇讓 1 重複，則最後的總和會變成 **123**，藉由比對 $2<3$ 可以輕易得知多出來的是 1。
+ 同理若是其他數字重複，我們只要看哪個位置比起全部只出現一次的總和多，就知道多出來的那個數字的二進位表示法。
+ **假如並沒有每個數字都出現過呢？**
+ 這種情況下，重複的數字可能出現了更多次。延續上面的例子，假如 1 重複了兩次，我們可以知道是答案是 1 。但當 1 重複了 3 次，我們要選一個數字被 1 取代，這個數字將不會出現在陣列當中。
+ 若我們選擇讓 2 被 1 取代，則總和變為 **114**。選擇 3 被取代，則結果變為 **113**。
+ 我們可以整理出一個規律：當重複的數字重複更多次時，在這個數字為 1 的位置，總和只可能會增加，不會變少。在這個數字為 0 的位置，總和只會減少不會增加。 e.g. 我們讓 1 重複更多次時，最低位的總和只會變更多或是不變，不管怎麼樣都會大於原本的 $2$。其他兩個位置的總和只會減少，不管怎麼樣都不會大於原本的總和。

## 程式碼解說

int findDuplicate(int *nums, int numsSize)
{
    int res = 0;
    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
    for (size_t i = 0; i < log_2; i++) {
        int bit = 1 << i;
        int c1 = 0, c2 = 0;
        for (size_t k = 0; k < numsSize; k++) {
            if (k & bit)
                ++c1;
            if (nums[k] & bit)
                ++c2;
        }
        if (c1 < c2)
            res += bit;
    }
    return res;
}

+ ==4==: 這裡我們根據 n 計算最多需要計算多少 bit。只要在 n 的 leading zero 區域，更小的數字都不可能會用到這些 bit。但我們實際會出現的數字範圍只有到 $n-1$，所以這裡可以這樣改成 `numSize-1`：

    const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize-1);

+ ==外層迴圈==：這裡我們走過每個需要看的 bit 位置。
+ ==內能迴圈==：這裡我們走過 $0\sim n-1$，一邊計算 $1\sim n-1$ 當中這個 bit 1 出現的次數 `c1`，一邊計算陣列中的數字裡 1 出現的次數 `c2`。最後比較 `c1 < c2` 就知道重複的數字在這個位置上是不是 1 了。如果是，就在 res 把對應的 bit 設為 1。
+ 走完所有 bit 位置後，就知道重複的數字長怎樣了。
$$
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
$$
## 實作改善
### 分析
+ 現有實作的缺點就是一定得走訪整個 `nums` $\log_2(n-1)$ 次，時間複雜度為 $O(n\log n)$，換來的則是 $O(1)$ 的空間複雜度。
+ Leetcode 上最快的實作是直接用一個長度 $n$ 的陣列紀錄數字是否出現過，如此通常不必走完整個陣列就完成任務了。缺點是 $O(n)$ 的儲存空間。
### 改善
+ 現有的實作可透過增加一個長度 $\log_2(n)$ 的陣列來累計每個位置的 `c2`，如此只要完整走訪整個陣列一次，在每個數字則利用 gcc extension 加速。如此用 $O(\log n)$ 的儲存空間換取到更短的時間。
+ 另外一點是，`c1` 事實上可以直接計算而不必實際走訪 $1\sim n-1$ 來累計。觀察以下二進位表，就可以發現規律。
| Decimal | Binary |
| ------- | ------ |
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
| 4 | 100 |
| 5 | 101 |
| 6 | 110 |
| 7 | 111 |
首先 $0\sim n-1$ 和 $1\sim n-1$ 的累計是一樣的。再來第 0 個 bit 是 2 個數字作為一個周期變化，每兩個數字中有 1 個為 1 。第 1 個 bit 則是 4 個數字成為一個周期，每 4 個數字中有 2 個為 1 。
如此根據 n ，我們可以計算出 bit $i$ 的累積結果：
\begin{align}
\floor{\frac{n}{2^{i+1}}} 2^i + \max(n\bmod{2^{i+1}},2^i)-2^i
\end{align}
+ Code

    int findDuplicate(int *nums, int n)
    {
        int res = 0;
        const size_t log_2 = 8 * sizeof(int) - __builtin_clz(n-1);
        int *c2 = calloc(log_2, sizeof(int));

        for (size_t i = 0; i < n; i++) {
            while(nums[i]) {
                ++c2[__builtin_ctz(nums[i])];
                nums[i] &= nums[i] - 1;
            }
        }

        for (size_t i = 0; i < log_2; i++) {
            int c1, r, bit = 1 << i;
            r = n & bit ? n & (bit-1): 0;
            c1 = ((n >> (i+1)) << i) + r;
            res |= (c1 < c2[i]) << i;
        }

        free(c2);
        return res;
    }

+ ==7~12==: 這裡走訪整個 `nums` 來統計各 bit 的累計次數。其中用到與 [quiz3-Bitmap](https://hackmd.io/xfEJ36T_QWyZPe2IAvB9dQ#%E6%B8%AC%E9%A9%97-5) 一樣的技巧，利用 ctz 來避免檢查每一個 bit 位置。
+ ==14~19==： 這裡檢查每一個 bit 位置，直接計算 `c1` 後，比較 `c1` 與 `c2` 來設定 `res`
+ 比較結果
+ 在 LeetCode 實測過後偶爾可以達到 4ms，原本則都是 8ms。
+ 以下為在我電腦上實測的結果，x 軸為 $n$，y 軸為執行時間。

+ 測試程式
:::warning
這裡測資的產生並不夠隨機，所以比較結果可能不公平，畢竟新方法會受到 set bit 數量而影響速度。
但平均來講新方法還是會比較快才對。
:::
:::spoiler

    #include <stdint.h>
    #include <stddef.h>
    #include <stdlib.h>
    #include <stdio.h>
    #include <time.h>

    #define MAX_N 20000

    int findDuplicate_improve(int *nums, int n)
    {
        int res = 0;
        const size_t log_2 = 8 * sizeof(int) - __builtin_clz(n-1);
        int *c2 = calloc(log_2, sizeof(int));

        for (size_t i = 0; i < n; i++) {
            while(nums[i]) {
                ++c2[__builtin_ctz(nums[i])];
                nums[i] &= nums[i] - 1;
            }
        }

        for (size_t i = 0; i < log_2; i++) {
            int c1, r, bit = 1 << i;
            r = n & bit ? n & (bit-1): 0;
            c1 = ((n >> (i+1)) << i) + r;
            res |= (c1 < c2[i]) << i;
        }

        free(c2);
        return res;
    }


    int findDuplicate(int *nums, int numsSize)
    {
        int res = 0;
        const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
        for (size_t i = 0; i < log_2; i++) {
            int bit = 1 << i;
            int c1 = 0, c2 = 0;
            for (size_t k = 0; k < numsSize; k++) {
                if (k & bit)
                    ++c1;
                if (nums[k] & bit)
                    ++c2;
            }
            if (c1 < c2)
                res += bit;
        }
        return res;
    }

    int main(void)
    {
        int *nums = malloc(sizeof(int) * MAX_N);
        nums[0] = 1;
        double time1=0, time2=0;
        for (int i=2; i < MAX_N; ++i) {
            nums[i-1] = i;
            nums[i] = 1;
            clock_t t1,t2; 

            t1 = clock(); 
            findDuplicate(nums, i + 1); 
            time1 += t1 = clock() - t1; 

            t2 = clock();
            findDuplicate_improve(nums, i + 1);
            time2 += t2 = clock() - t2;

            printf("%d, %.8f, %.8f\n", i + 1,
                (double)t1 / CLOCKS_PER_SEC, (double)t2 / CLOCKS_PER_SEC); // in seconds 
        }
        printf("%.8f, %.8f\n", time1 / CLOCKS_PER_SEC, time2 / CLOCKS_PER_SEC); // in seconds 
        return 0;
    }

:::