# 2020q3 Homework6 (quiz6)
contributed by < `ptzling310` >
>[2020q3 第 6 週測驗題](https://hackmd.io/@sysprog/2020-quiz6)
---
## 測驗 `1`： bfloat16

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 &= BB1;
    r /= 256;
    y = x + r;

    *py &= BB2;
    return y;
}

### 程式

    exp = *py & 0x7F800000u;
    man = *py & 0x007FFFFFu;

`exp` 是取出 `y` 的 Exponent(E) 的部分，共 8 bits。
`man` 是取出 `y` 的 Fraction(F) 的部分，共 23 bits。

    if (!exp && !man) /* zero */           
        return x;

如果 `exp` 以及 `man` 皆為 0 表示該 float point 為 `±0`。

    if (exp == 0x7F800000u) /* infinity or NaN */
        return x;

digraph structs {
	node[shape=record]
    
    NaN[label="NaN",shape=plaintext];
	struct1 [label="0/1|11111111|nonZero"];
    {rank= NaN; struct1}
    
    INF[label="INF",shape=plaintext];
	struct2 [label="0/1 | 11111111| 0..0"];
    {rank= INF; struct2}
}

若 Exponent(E) 的部分皆為 1 ，則為 NaN 或 INF 的情況，故 `retrun x`即可。

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

目前：`*pr`=`r` = `x` ； `*py` = `y` = `x`。
此段進行進位處理。
假設目前一 float point ： ($b_{31}|b_{30}b_{29}b_{28}...b_{23}|b_{22}...b_{16}b_{15}...b_0$)~2~，其中：$b_{31}$ 是 Sign(S)；$b_{30}-b_{23}$ 是 Exponent(E) 的部分；$b_{22}-b_{16}$ 共 7 bits 應為要保留的小數點，再來要經由$b_{15}$ 來判斷是否該進位。
在 line `17` 中，`x+r` 後會使進位達成，也就是說若 `x` 的 $b_{15}$ 為 bit 1，則會進位。故 `r` 的 Fraction(F) 應該為 (000000010...0)~2~。

`x` = $(-1)^{S}\times1.fraction\times2^E$，`r`=$(-1)^{S}\times1\times2^E$。
於 line `16`：`\256` = $÷2^8$，故 `r/256` = $(-1)^{S}\times2^E÷2^8=(-1)^{S}\times2^{E-8}$。

於 line `17`：`y=x+r` ：
$\begin{aligned}x+r&=(-1)^{S}\times1.fraction\times2^E+(-1)^{S}\times2^{E-8}\\
&=(-1)^{S}\times2^{E}\times(1.fraction+2^{-8}) \\
&=(-1)^{S}\times2^{E}\times(1.fraciton+0.000000001)\end{aligned}$

    *py &= BB2;

由於最終只保留$b_{31}-b_{16}$的部分，所以$b_{15}-b_0$ (共 16 bits) 清除為0。故 BB2 =`0xffff0000`。

-----------
## 測驗 `2`： Ring buffer

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

::: spoiler 測試程式碼

#include <assert.h>

RINGBUF_DECL(int, int_buf);

int main()
{
    int_buf my_buf;
    RINGBUF_INIT(my_buf, 2, int);
    assert(is_ringbuf_empty(&my_buf));

    ringbuf_write(&my_buf, 37);
    ringbuf_write(&my_buf, 72);
    assert(!is_ringbuf_empty(&my_buf));

    int first;
    ringbuf_read(&my_buf, first);
    assert(first == 37);

    int second;
    ringbuf_read(&my_buf, second);
    assert(second == 72);

    return 0;
}

:::

### Function
#### RINGBUF_DECL

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

Ring buffer 會有紀錄
- `size`：紀錄此 buffer 大小
- `start`：紀錄第一筆資料的位子。
- `end`：紀錄最後一筆資料的下一格位子。
- `elemnets`：型態為 T 的資料。

#### RINGBUF_INIT

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

Parameters：
- `BUF` ：這個 buffer 的變數名稱。
- `S` ：這個 buffer 的大小。
- `T` ：這個 buffer 所存的類型。

這裡是在建立一個新的 ring buffer，且大小為輸入的 `S+1`。

#### NEXT_START_INDEX
判斷接下來 `start` 的位子。

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

若 `start` 已在 buffer 的最後一格，則 `start` 則移動至第一格，已達 ring 的效果；若無，則將 `start` 往後一格。故 RB1 =`1`。

#### NEXT_END_INDEX(BUF)
判斷接下來 `end` 的位子。

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

若 `end` 未達最後一格(`size`)，則可將 `end` 往後一格；若已達 `size`，則將 `end` 移到第一個位子，此舉即可達 ring 的效果。故 RB2 = `1`。

#### is_ringbuf_empty

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

若 `start` 與 `end` 指向同一格，則表示此 buffer 為 empty。

digraph structs 
{
	node[shape=record]
	struct [label="<f0>||||<f1>"];
    start[label="start",shape=plaintext];
    end[label="end",shape=plaintext];
    start->struct:<f0>
    end->struct:<f0>
}

#### is_ringbuf_full

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

如果下一筆資料會被放在與 `start` 相同的位子，代表此 buffer 已滿。

digraph structs 
{
	node[shape=record]
	struct [label="<f0>1|2|3|4|<f1>5"];
    start[label="start",shape=plaintext];
    end[label="end",shape=plaintext];
    start->struct:<f0>
    end->struct:<f1>
}

#### ringbuf_write_peek

#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]

會將東西填入 buff 的 `end` 處。

#### ringbuf_write_skip

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

在 line `27` 先找到下一個 `end` 所在的位子。
若此 buffer 是 empty ，表示接著要寫入的資料會為第一筆資料，所以 `start` 也要跟著移動到該筆資料的位子。

#### ringbuf_read_peek

#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]

取出 `start` 所指的位子的 elemetnt。

#### ringbuf_read_skip

#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);

將 `start` 指到下一個位子。

#### ringbuf_write

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

Parameters：
- BUF：這個 buffer 的變數名稱。
- ELEMENT：所想要寫入的值。

藉由呼叫 `ringbuf_write_peek` 會將此值填 `end` 所指的位子。再由 `ringbuf_write_skip` 將 `end` 移動到下一個該指向的位子。

#### ringbuf_read

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

呼叫 `ringbuf_read_peek` 讀取 element，再將 `start` 移動到正確的位子。

--------------------
## 測驗 `3`： Linked list

#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) {
        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;
}

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

### 程式
#### cons(x,y)

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

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

此處是將 `x` 以及 `y` 連結，但這邊要注意是將 `y` 擺在 `x` 前方。
利用 compound literals 來將 `y`以及`x` 配給 `struct` 中的 `val` 以及 `next`。
即：

.val = y;
.next = x;

所以在 line `39`：

digraph structs 
{
    rankdir=LR
	node[shape=record]
	A [label="A"];
    B [label="B"];
    NULL[label="NULL",shape=plaintext];
    D->C->B->A->NULL
}

#### sort

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

將 link list 進行 insertion sort。

#### sorted_insert

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

`node` 是指本次要往前插入的 node，會經由 `while` 找到適合的位子並且將 node 插入。
若沒有 `head` 或者 `node` 會位在第一個位子時，便將 `node` 設為 `head`。
故 SS1 = `node->next = *head`； SS2 = `*head = node`。

--------------------
## 測驗 `4`： [LeetCode 287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)
值會在 **1 <= nums[i] <= n**。

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

### 概念
舉例：1,3,4,2,2，`n`= 4。
所以出現的數字會有 1~4，將每個數字用二進制表示，再將 b~i~ 加總。
| number | b~2~ | b~1~ | b~0~
| -------- | -------- | -------- |-------- |
| 1 | 0 | 0 |1 |
| 2 | 0 | 1 |0 |
| 3 | 0 | 1 |1 |
| 4 | 1 | 0 |0 |
| sum | 1 | 2 | 2 |
如果今天重複的是 2=(010)~2~，則會發現 b~1~ 會多出 1。

### 程式

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

`log_2` 是用來判斷說我們所需計算幾個 bit 的加總。

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

`k` 會是 1~n ， 所以 `c1` 是用來紀 b~i~ 之 bit 1 個數；`c2` 就是紀錄在陣列中 b~i~ 之 bit 1 個數。

        if (CCC)
            res += bit;

若 `c2` 比較大，代表 b~i~是有多出的數字，則將此 bit 記錄到 `res` 中。
最後 `res` 所存的值就會是重複的數字。

###### tags: `sysprog2020`