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

## 測驗 1
浮點數結構分為 sign, exponent, fraction 三個部分，而浮點數的值為 $2^{(exponent-127)} \times (1 + fraction)$，且 sign 決定正負號，其中 fraction 的計算是最左邊的 bit 為 $2^{-1}$，第 2 個為 $2^{-2}$，以此類推。

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.140625=40490000
3.140625=40490000
1.200000=3f99999a
1.203125=3f9a0000
2.310000=4013d70a
2.312500=40140000
3.460000=405d70a4
3.453125=405d0000
5.630000=40b428f6
5.625000=40b40000

這題可以先從執行結果看起，可以看到會將原本(十六進位)的第 5 個位數做"七捨八入"，再把後面的位數捨去，換成二進位來說，是將第 17 位元加 1 後捨去 17 和後面的位元。

前面 5 ~ 10 行在判斷輸入的 x 是否為 0 或無限或 NAN，是的話直接返回原值，因為轉換後不影響值。
第 15 行 `*pr &= 0xff800000;` 是為了取出 sign bit 和 exponent bits。
第 16,17 行用例子比較好解釋，可以先將原本的 x 當作 $1.xx \times 2^k$ (負數則是 $1.xx \times -2^k$)，
`*pr &= 0xff800000;` 後 r 變成 $2^k$ (x 為負數時 $-2^k$)，
`r /= 256` 後 r 變成 $2^{k-8}$ ($-2^{k-8}$)，
`y = x + r` 的 y 為 $1.xx \times 2^k + 2^{k-8} = 2^k \times (1.xx + 2^{-8})$ ，相當於原本的 x 的第 17 位元加 1。
(x 為負數時則是 $1.xx \times -2^k + (-2^{k-8}) = -2^k \times (1.xx + 2^{-8})$，一樣成立)
`*py &= 0xffff0000;` 則是將後面 16 個位元捨去，如此一來就達到預想的輸出結果了。
## 測驗 2

#define RINGBUF_DECL(T, NAME) \
    typedef struct {          \
        int size;             \
        int start, end;       \
        T *elements;          \
    } NAME

#define RINGBUF_INIT(BUF, S, T)             \
    {                                       \
        static T static_ringbuf_mem[S + 1]; \
        BUF.elements = static_ringbuf_mem;  \
    }                                       \
    BUF.size = S;                           \
    BUF.start = 0;                          \
    BUF.end = 0;

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

#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
#define ringbuf_write_skip(BUF)                   \
    do {                                          \
        (BUF)->end = NEXT_END_INDEX(BUF);         \
        if (is_ringbuf_empty(BUF))                \
            (BUF)->start = NEXT_START_INDEX(BUF); \
    } while (0)

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

#define ringbuf_write(BUF, ELEMENT)        \
    do {                                   \
        ringbuf_write_peek(BUF) = ELEMENT; \
        ringbuf_write_skip(BUF);           \
    } while (0)

#define ringbuf_read(BUF, ELEMENT)        \
    do {                                  \
        ELEMENT = ringbuf_read_peek(BUF); \
        ringbuf_read_skip(BUF);           \
    } while (0)

這題用了一個大小為 size + 1 的 array 做為 ring buffer。

可以先從 `ringbuf_write` 看起，可以看到 `ringbuf_write` 會先在 end 的地方寫入值，再做 `ingbuf_write_skip`，因此可以推測 `ringbuf_write_skip` 是在把 end 的位置更新。到這裡為止，可以知道 `NEXT_END_INDEX` 是在把 end 的位置往後推一位，而如果到 array 尾端的話，就把 end 改到 0，所以 RB2 = 1。`ringbuf_read` 的部分大致相同，所以也可以推斷出 RB1 = 1。

而 `ringbuf_write_skip` 中除了做 `(BUF)->end = NEXT_END_INDEX(BUF);` 外，還有判斷 `is_ringbuf_empty` (end == start)，如果成立的話，`(BUF)->start = NEXT_START_INDEX(BUF);`。
這個部分也是為什麼要用 size + 1 的 array 的原因。假設 start 現在是 0，end 是 size，也就是 array 中有 size 個元素，如果這時要再寫入的話，end 會移到 0，觸發 start 往後移一位。因為讀取是從 start 開始讀，所以即使 array 中現在有 size + 1 個元素了，ring buffer 還是只有 size 個元素。

假設 ring buffer size = 7，使用者原本輸入 1234567

digraph {
    start [shape = plaintext]
    end [shape = plaintext]
    rb [label = "<0>1|2|3|4|5|6|7|<8>" shape = record] 
    start -> rb:<0>
    end -> rb:<8>
}

再寫入 8 :

digraph {
    start [shape = plaintext]
    end [shape = plaintext]
    rb [label = "<0>1|<1>2|3|4|5|6|7|<8>8" shape = record] 
    start -> rb:<0>
    end -> rb:<8>
}

digraph {
    start [shape = plaintext]
    end [shape = plaintext]
    rb [label = "<0>1|<1>2|3|4|5|6|7|8" shape = record] 
    start -> rb:<0>
    end -> rb:<0>
}

digraph {
    start [shape = plaintext]
    end [shape = plaintext]
    rb [label = "<0>1|<1>2|3|4|5|6|7|8" shape = record] 
    start -> rb:<1>
    end -> rb:<0>
}

## 測驗 3

#include <stdio.h>

/* clang-format off */
#define cons(x, y) (struct llist[]){{y, x}}
/* clang-format on */

struct llist {
    int val;
    struct llist *next;
};

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

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

int main()
{
    struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
    struct llist *p;
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");

    sort(&list);
    for (p = list; p; p = p->next)
        printf("%d", p->val);
    printf("\n");
    return 0;
}

這題在實作一個 singly-linked list 的 insertion sort。`sorted_insert` 這個 function 將 node 依照 increasing order 插入 list 中(可以從執行結果看出)，根據第一周的訓練，
可以得到 `SS1 = node->next = *head`, `SS2 = *head = node`，這裡的判斷是如果 head 不存在或是 node value <= head value 時，將 node 插到第一個位置，並將 head 改為 node。而 20 ~ 23 行則是依照 insertion sort 的方法，將 node 插到正確的位置。

`sort` 這個 function 是先建立一個叫做 sorted 的空白 list，並將要做 sorting 的 list 的元素一個個用 `sorted_insert` 插入到 sorted 中，這樣最後 sorted 就會是以排序好的狀態。

A, B, C, D 的值可以參考 [C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick#inode) 裡的靜態 linked list。需要注意的是這裡是

#define cons(x, y) (struct llist[]){{y, x}}

struct llist {
    int val;
    struct llist *next;
};

x 是 `*next` 而 y 是 val，所以 head 是最外圍的 D，並依序往內。因此 A = 7, B = 4, C = 5, D = 9。
## 測驗 4
給定一個整數序列，其中會有一個數值重複，請找出。
已知條件：

1. 假設陣列長度為 $n$，數值的範圍是 $1$ 到 $n−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 (CCC)
            res += bit;
    }
    return res;
}

第四行 `const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);` 其實等於
`32 - __builtin_clz(numsSize)`，所以是在求 numsSize 的 MSB，因為數值範圍是 1 到 numsSize - 1，所以這裡其實可以用 `__builtin_clz(numsSize - 1)`，不過影響不大。

接著第一個 for loop 在做的是對逐個 bit 做檢查，c1 紀錄的是從 0 到 numsSize - 1 總共在該 bit 有幾個 1-bits，c2 則是給定的陣列裡面總共在該 bit 有幾個 1-bits。可以想見的是，如果重複的數在該 bit 是 0，c1 會大於等於 c2 (因為重複的數出現意味著壓縮其他在該 bit 為 1 的數字出現的機會)，而如果重複的數在該 bit 是 1，c1 會小於 c2。

舉例來說，如果今天數值範圍是 1 ~ 3，c1 會記錄 0 ~ 3 在各個 bit 上有幾個 1，在最後一位上有 2 個 1，在倒數第二位上有 2 個 1。c2 紀錄 nums[0] ~ nums[3] 在各個 bit 上有幾個 1。如果現在重複的是 1，可能是 [1,1,2,3], [1,1,1,2], [1,1,1,3], [1,1,1,1] (順序不計)，在最後一位時，c2 分別是 3, 3, 4, 4，倒數第二位時，c2 分別是 2, 1, 1, 0。所以可以得到重複的數最後一位是 1，倒數第二位是 0。

因為第 14 行 CCC 成立時 `res += bit;`，所以可以知道 `CCC = c1 < c2`

### 延伸問題

#### 實作不同的程式碼 (合法的 C 程式，可運用 GNU extension)，使其表現優於上述程式碼

int findDuplicate(int *nums, int numsSize)
{
    int bk[numsSize];
    memset(bk, 0, sizeof(bk));
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == bk[nums[i]])
            return nums[i];
        bk[nums[i]] = nums[i];
    }
    return 0;
}

蠻直觀的作法，運用 bucket sort 的概念，一開始先設一個全部數值皆為 0 的 array，如果檢查到nums 中有 nums[i] == bk[nums[i]]，代表該數重複了，所以 return nums[i]。反之將
bk[nums[i]] = nums[i]，這樣下次重複時就能發現。

這樣做的好處是當有重複數字出現時會馬上結束，壞處是需要額外 O(n) 空間。另外因為 leetcode 不會將上次結果清除，所以第四行的 memset 一定要做。