---
# System prepended metadata

title: 2020q3 Homework6 (quiz6)
tags: [進階電腦系統理論與實作]

---

# 2020q3 Homework6 (quiz6)
contribute by < `Liao712148` >

> 重做[第6周測驗題](https://hackmd.io/@sysprog/2020-quiz6#%E6%B8%AC%E9%A9%97-1)
###### tags: `進階電腦系統理論與實作` 

### 測驗1
```cpp=
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;
}
```
透過第`3`行可以把數值用 16 進位的方式表示，
`exp`把`float32`中的`exponent`存起來，`man`把`float32`中的`mantissa`存起來，
然後再檢查是否數值落在`zero`或`NaN`的範圍，因為`Bfloat16`只有 16 位元可以儲存，而且對照`float32`的話前`9` 項 bit 是維持不動的，所以要將前 9 項存起來，因此`BB1`要選`0xff800000`，表示把前 9 項保留，其餘的 bit 清除。
但是因為 `Bfloat16` 在`mantissa`項比` float32` 少了 16 個 bit，所以勢必要作一些 `rounding`，這裡用的方式是讓 `mantissa` 的第七項之後無條件進位。對照的程式碼是`16,17`行
最後再保留前 16 個 bit 即可，因此 `BB2` 要選擇 `0xffff0000`。
:::danger
:warning: 中英文之間用一個半形空白字元區隔，注意共筆書寫規範
:notes: jserv
:::

#### 延伸題目


### 測驗2

```cpp=
#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)
```
此題用了大量的`macro`而不是用函式呼叫，是因為呼叫函式需要花費的時間及空間成本較大，例如`stack`要存放函數的`loacl variable`及回傳地址的資訊。而如果函式執行較為簡單的程式的話，可以改用`macro`，直接在程式中展開，而`do{...}while(0)`可以避免`danging else`的情況發生。
`danging else`:因為無法事先知道`marco`會在哪裡被使用，如果是在`if else`的情況下被使用的話，加上`marco`中又碰巧定義了`if else`，則外面的`if`會找到`marco`中的`else`，造成外面的`else`沒有對應到`if`
```cpp=
#define CALL_FUNCS(a){ if(condition){...}else{,,,}}
int main()
{
    if(condition)//這裡的if會找到CALL_FUNCS中的else
        CALL_FUNCS(a);
    else
        bar(a);//使得這個else沒有對應到的if，造成danging else
    return 0;
}
```
此題是`ring buffer`的實踐，透過`RINGBUF_DECL`行建立一個名為`my_buf`的`struct`，在透過`RINGBUF_INIT`行將`struct`初始化，其中建立`static int static_ringbuf_men[]`的陣列使得該`marco`執行完後`static-ringbuf_menp[]`會繼續存在，再透過`ringbuf_write`將要儲存的數值存入，而在寫入的過程中，需要注意`ring buf`是否已經存滿了數值，如果`my_buf.end`與`my_buf.start`相同的話表示已經存滿了。
如果存滿則將`my_buf.end`設定為`my_buf.start`的地方，並且將`my_buf.start`設定為下一格，如果沒有滿則只需要將`my_buf.end`往後一格即可，`my_buf.start`不用作調整。
所以`RB1,RB2`都要選擇`1`。


以下補充`ring buffer`的特色:
在透過陣列實踐`Queue`時，如果一直`dequeue`則會將`front`不斷往`back`移動，如果不作資料的搬移的話，那這樣看似`front`前面還有很多格子可以儲存，但卻無法有效利用。而`ring biffer`以讓隊頭隊尾的指標繞回陣列開始的位置，這樣就可以避免以上的情況發生。
![queue](https://miro.medium.com/max/500/1*wN83zdV3arHyUl5GQXxRfw.jpeg)


### 測驗3
```cpp=
#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;
}
```
此題是單向linked list 的另外一種實作方式，透過`cons(x,y)`不斷串接`node`，其中`y`用來初始化`llist`中的`next`，`x`用來初始化`llist`中的`value`，是屬於`compile time memory allocation` or `static memory allocation`而如果使用`malloc`則是屬於`runtime memory allocation `or `dynamic memory allocation`。可以參考[Compile time vs runtime memory allocation difference](https://codeforwin.org/2018/05/compile-time-and-runtime-memory-allocation.html)
依照題目要求的存放順序，所以`A`選`7`,`B`選`4`,`C`選`5`,`D`選`9`。
接著是透過`insertion sorted`將資料進行排序所以`SS1`選` node->next = *head
`,`SS2`選`*head = node`



### 測驗4
```cpp=
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.假設陣列長度為n，數值的範圍是1到n−1
2.重複的數值不一定只重複一次

所以我們可以算出如果每個數字都只出現一次的話，若以`bit`的方式表達，會是怎樣的分布。透過第`4`行可以知道`numsSize`要用幾個`bit`表達，以減少不必要的位元運算。接著如果某一數值被比它小的數取代，則比它小的數合計的位元數會大於每個數字都只出現一次的情況，如過是被大的數取代則相反，透過第`8`行的`for`可以算出該項`bit`是否有重複出現，再把重複出現的`bit`對應到的數值加總起來即為所求。