# 2020q3 Homework6 (quiz6)
contributed by < `dalaoqi` >
## 測驗一
此題是要將 IEEE 754 的 FP32 (Single-precision floating-point format) 轉換成精度較低，動態範圍與 FP32 相同的 bfloat16。
bfloat16 與 FP32 最大的不同在於 fraction 只有用 7 個 bit。
```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;
}
```
* 程式在轉換前會先對幾種特殊值做判斷
* 當 `exp` 和 `man` 都為 0，代表輸入的數值為 0 ，不做處理直接回傳。
* 當 `exp == 0x7F800000u` ，輸入的值的 exponent 全為 1，可能為 正負無限大或是 `NaN`。
* 可以知道最後程式回傳的會是 bfloat16 的值，因此在回傳前需要捨去後面的 16 位元，所以 `BB2` 為 `0xffff0000`
* 在捨去後 16 bit 前，需要判斷是否要對第 8 位元做 rounding
* 一開始程式會先去保留 exponent 的部分，所以 `BB1` 為 `0xff800000`
* 而後 r 會除上 256，r 的 MSB 會向右 shift 8 bit。也就是說如果 r 的 MSB 若為 1 會達成進位的條件。
## 測驗二
考慮以下 ring buffer 的實作:
```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)
```
ring buffer 需要去特別注意的地方為當 buffer 為空或是滿的情況。
此題的 `NEXT_START_INDEX` 及 `NEXT_END_INDEX` 主要是因為當在紀錄資料的時候 `START` 和 `END` 會根據資料的進出而改變位置，因此需要注意當超出 buffer 的大小時，要回到 0 的位置。
## 測驗三
考慮到以下靜態初始化的 singly-linked list 實作:
```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;
}
```
參考 [C 語言程式設計技巧](https://hackmd.io/@sysprog/c-trick)
* 這裡在 macro 中使用 Compound literals 去建立靜態的 linked list
```cpp
#define cons(x, y) (struct llist[]){{y, x}}
```
* 可針對未知大小的 array/struct 初始化，也可以直接對特定位置的 array 或 struct 的內容賦值
* compound literal 可以做 lvalue ，可以傳特定型別或自己定義的 struct
> C99 [6.5.2.5] Compound literals
> * The type name shall specify an object type or an array of unknown size, but not a variable length array type.
> * A postfix expression that consists of a parenthesized type name followed by a braceenclosed list of initializers is a compound literal. It provides an unnamed object whose value is given by the initializer list.
> * If the type name specifies an array of unknown size, the size is determined by the initializer list as specified in 6.7.8, and the type of the compound literal is that of the completed array type. Otherwise (when the type name specifies an object type), the type of the compound literal is that specified by the type name. In either case, the result is an lvalue.
將 `struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);` 以下為展開後的樣子
```graphviz
digraph G {
graph[pencolor=transparent];
rankdir=LR
D[shape=box];
C[shape=box];
B[shape=box];
A[shape=box];
NULL[shape=none,label="NULL"];
D->C->B->A->NULL;
}
```
* 輸出結果為 9547，因此 D = 9、C = 5、B = 4、A = 7。
接下來程式碼會對此串列進行插入排序 (Insertion Sort)，包含 `sort` 及 `sorted_insert` 兩個函式。
`sort` 函式會迭代的取出串列的值，取出值迴後ˋ會去呼叫 `sorted_insert` 去找出該值在 sorted 中適合的位置。
`SS1` 和 `SS2` 這裡，是在判斷要排序的值是否小於 `*head`，也就是小於 sorted 的第一個元素，如果是，則需要和他交換，因此 `SS1` 為 `node->next = *head`、`SS2` 為 `*head = node`。
## 測驗四
LeetCode [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/) 給定一個整數序列，其中會有一個數值重複，請找出。
考慮以下程式碼是可能的解法:
```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;
}
```
一開始的 `const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);`是用來判斷 `numSize` 最少需要用幾個 bits 表示。
根據題目給的條件可以得知：對於一個長度為 n 的陣列，數字的範圍是 $1$ 到 $n-1$ ，重複的只有一個。
* 假設 `nums[4] = {1, 2, 3, 4}`
* | Dec | Bin |
| -------- | -------- |
| 0 | 000 |
| 1 | 001 |
| 2 | 010 |
| 3 | 011 |
* index: 0 + 1 + 2 + 3 第一個 bit 總和 = 2
* nums[index]: 1 + 2 + 3 + 1 第一個 bit 總和 = 3
* 從上述的描述可以發現，只要有重複的數值，nums 在 bit 為 1 的個數總和會比 index 在 bit 為 1 的個數總和還要多。
* 在程式的兩個迴圈中，會去逐一檢查陣列中的每個數值的每個 bit，
* `c1` 為 index 加總
* `c2` 為 nums[index] 加總
因此 `CCC` 應為 `c1 < c2`。
Sign in with Wallet
Connect another wallet