# 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`以讓隊頭隊尾的指標繞回陣列開始的位置，這樣就可以避免以上的情況發生。
### 測驗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`對應到的數值加總起來即為所求。
Sign in with Wallet
Connect another wallet