# 2020q3 Homework6 (quiz6)
contributed by < `ptzling310` >
>[2020q3 第 6 週測驗題](https://hackmd.io/@sysprog/2020-quiz6)
---
## 測驗 `1`： bfloat16
```c=
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;
}
```
### 程式
```c=5
exp = *py & 0x7F800000u;
man = *py & 0x007FFFFFu;
```
`exp` 是取出 `y` 的 Exponent(E) 的部分，共 8 bits。
`man` 是取出 `y` 的 Fraction(F) 的部分，共 23 bits。
```c=7
if (!exp && !man) /* zero */
return x;
```
如果 `exp` 以及 `man` 皆為 0 表示該 float point 為 `±0`。
```c=9
if (exp == 0x7F800000u) /* infinity or NaN */
return x;
```
```graphviz
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`即可。
```c=12
/* 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}$
```c=
*py &= BB2;
```
由於最終只保留$b_{31}-b_{16}$的部分，所以$b_{15}-b_0$ (共 16 bits) 清除為0。故 BB2 =`0xffff0000`。
-----------
## 測驗 `2`： Ring buffer
```c=
#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 測試程式碼
```c
#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
```c
#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
```c=8
#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` 的位子。
```c=17
#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` 的位子。
```c=19
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)
```
若 `end` 未達最後一格(`size`)，則可將 `end` 往後一格；若已達 `size`，則將 `end` 移到第一個位子，此舉即可達 ring 的效果。故 RB2 = `1`。
#### is_ringbuf_empty
```c=21
#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
```
若 `start` 與 `end` 指向同一格，則表示此 buffer 為 empty。
```graphviz
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
```c=22
#define is_ringbuf_full(BUF) (NEXT_END_INDEX(BUF) == (BUF)->start)
```
如果下一筆資料會被放在與 `start` 相同的位子，代表此 buffer 已滿。
```graphviz
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
```c=24
#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
```
會將東西填入 buff 的 `end` 處。
#### ringbuf_write_skip
```c=25
#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
```c=32
#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
```
取出 `start` 所指的位子的 elemetnt。
#### ringbuf_read_skip
```c=33
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);
```
將 `start` 指到下一個位子。
#### ringbuf_write
```c=35
#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
```c=41
#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
```c=1
#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)
```c=4
/* 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`。
即：
```c
.val = y;
.next = x;
```
所以在 line `39`：
```graphviz
digraph structs
{
rankdir=LR
node[shape=record]
A [label="A"];
B [label="B"];
NULL[label="NULL",shape=plaintext];
D->C->B->A->NULL
}
```
#### sort
```c=26
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
```c=12
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**。
```c=
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。
### 程式
```c=4
const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
```
`log_2` 是用來判斷說我們所需計算幾個 bit 的加總。
```c=5
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 個數。
```c=14
if (CCC)
res += bit;
```
若 `c2` 比較大，代表 b~i~是有多出的數字，則將此 bit 記錄到 `res` 中。
最後 `res` 所存的值就會是重複的數字。
###### tags: `sysprog2020`
Sign in with Wallet
Connect another wallet