# 2020q3 Homework6 (quiz6)
contributed by < `ccs100203` >
###### tags: `linux2020`
> [第 6 週測驗題](https://hackmd.io/@sysprog/2020-quiz6)
## 測驗 1
將 [FP32](https://en.wikipedia.org/wiki/Single-precision_floating-point_format) 轉換為 [bfloat16](https://en.wikipedia.org/wiki/Bfloat16_floating-point_format)
```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 &= 0xff800000;
r /= 256;
y = x + r;
*py &= 0xffff0000;
return y;
}
```
以下為測試程式
```cpp=
void print_hex(float x) {
int *p = (int *) &x;
printf("%f=%x\n", x, *p);
}
int main() {
float a[] = {3.140625, 1.2, 2.31, 3.46, 5.63};
for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
print_hex(a[i]);
float bf_a = fp32tobf16(a[i]);
print_hex(bf_a);
}
return 0;
}
```
- `int *py = (int *) &y;` 利用 pointer 的方式去做轉換，而不是做 `int py = (int) y;` ，差別在於後者會無條件捨去至整數，而前者會將 IEEE 754 的 bit 完整保留至 `py` 內。做轉換的目的在於對 integer 做 bitwise 操作，因為 float 不能做 bitwise 的操作。
- `exp` 及 `man` 分別是指數與尾數的部分，用來判斷 Boundary value，排除掉 Normalized number 以外的數值，參照以下的表
- 再來要對 Normalized number 做 round，這邊做 round 的方式是
1. 利用 `*pr &= 0xff800000;` 只保留 sign 與 exp 的部分
2. 接著 `r /= 256` 是為了 rounding。原理是在經過上面只保留前面後，`r` 會是 $2^n * 1.00000...$ 在 IEEE 754 的規範中他會是第 9 位，這時做 `r /= 256` 變成 $2^{n-8} * 1.00000...$ 後他會是 BFloat 16 規範外的第一個 bit，此時利用他與原本的 `x` 做相加就可以判定最後是否進位。
只保留 sign 與 exp 的`r` 會是 $0\overbrace{xxxxxxxx}^\text{8}\overbrace{0000000}^\text{7}$，故除 256 之後就會是 BFloat 16 外的第一個位置
3. 將原本的數值 `x` 加上剛剛運算出的值 assgin 給 `y`
4. 利用 `*py &= 0xffff0000;` 只保留 `y` 最前方的 16 bits，以符合 BFloat 16 的規範
## 測驗 2
[ring buffer](https://en.wikipedia.org/wiki/Circular_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)
```
對應的測試程式:
```cpp=
#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;
}
```
### 為什麼需要 `do {...} while(0)`
根據 [do/while(0) vs scope block](https://stackoverflow.com/questions/1067226/c-multi-line-macro-do-while0-vs-scope-block) 的解釋，使用這個寫法可以避免 dangling else 的出現。
```cpp
if (<condition>)
call_macro(a);
else
bar(a);
```
如果 macro 內只使用 `{ }`，程式展開後會變成
```cpp
if (<condition>)
{
statements
};
else
bar(a);
```
可以注意大括號後面會有 ==;==，這會導致 if 判斷式到這裡就結束，else 獨立出來而導致編譯失敗。
一個解決方法是拿掉呼叫 macro 時的 ==;==，但這並不是一個優雅的解法，因為這會導致 coding style 不一致。
```cpp
if (<condition>)
call_macro(a)
else
bar(a);
```
較為優雅的解法就是使用 do while(0)，要注意第 4 行， macro 內的 while(0) 後方不能有 ==;==，否則將失去這樣寫的用意。可以看到程式展開之後將變成下面的樣子
```cpp=
#define call_macro(x) \
do { \
statements \
} while (0)
if (<condition>)
do{
statements
}while(0);
else
bar(a);
```
### 程式原理
解釋 ring buffer 運作模式
- `ringbuf_write`
- 呼叫 `ringbuf_write_peek`，將 `ELEMENT` 放進 `end` 的位置
- 呼叫 `ringbuf_write_skip`，將 `end` 指向下一個位置。當 `start == end` 時，會將 `start` 指向下一個位置，我想是因為 buffer 滿了，捨棄掉 buffer 內存放最久的 element。
- `ringbuf_read`
- 呼叫 `ringbuf_read_peek`，將 `start` 指向的 `ELEMENT` 讀出來
- 呼叫 `ringbuf_read_skip`，將 `start` 指向下一個位置。
- 使用到 `NEXT_START_INDEX` 或 `NEXT_END_INDEX` 時，都是為了把指針指向下一個位置，所以都需要做 ==+ 1==，由此可以選出答案。
:::warning
好奇 `ringbuf_read_skip` 並不像 `ringbuf_write_skip` 當 buffer 在極值時有做判斷。如果 buffer 是空的而直接做 `ringbuf_read`，`start` 就會領先 `end`，變成要繞一圈 buffer 才會讀到後來 `ringbuf_write` 放入的值。
:::
## 測驗 3
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) {
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, 7), 4), 5), 9);
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;
}
```
執行結果為:
```
9547
4579
```
- 這題使用到 [compound literal](https://gcc.gnu.org/onlinedocs/gcc/Compound-Literals.html) 的技巧，`#define cons(x, y) (struct llist[]){{y, x}}`，不過老師為了看大家夠不夠細心故意把 x, y 相反哈哈。
- 題目的 sort 是做 insertion sort，巡遍整個 linked-list 由小到大排序，題目問的部分是當他為 第一個值 or 最小的值，要放在 linked-list 最前面時要怎麼做。由於 `node` 要放到最前面，所以直接將 `node->next` 接上 `*head`，接著要對 `*head` 進行更新，所以 assign `node` 給 `*head`。
```cpp=14
if (!*head || (*head)->val >= node->val) {
node->next = *head;
*head = node;
return;
}
```
- 剩下的部分是 node 要插入在第一個位置以外的地方的情況，就是會先在 list 內不斷往後找直到有 value 比要插入的 node 大，或是已經巡遍到最後了，就會把 node 插入。
```cpp=20
while (current->next && current->next->val < node->val)
current = current->next;
node->next = current->next;
current->next = node;
```
## 測驗 4
LeetCode [287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)給定一個整數序列，其中會有一個數值重複，請找出。
已知條件：
1. 假設陣列長度為 $n$，數值的範圍是 $[1, n-1]$
2. 重複的數值不一定只重複一次
3. 範圍內的其他數字都只會出現一次
```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 (c1 < c2)
res += bit;
}
return res;
}
```
程式利用每個 bit 出現的次數去比對此數字有沒有出現過多次，當 理論上會出現的次數 (`c1`) < 實際上出現的次數 (`c2`) 時，代表這個 bit ==出現次數過多==，即為答案內的 bit。
理論上會出現的次數(`c1`): 1 ~ `numsSize` 的數字每個 bit 的總和，
e.g. 1~3
| decimal | binary |
| :--: | :--: |
| 1 | 0001 |
| 2 | 0010 |
| 3 | 0011 |
每個 bit 的總和就會是 0 0 2 2
- 以下是一步一步解說:
1. log2 是為了知道總共需要比較幾個 bit
2. `bit = 1 << i` 這邊就是每一次迴圈需要比對的 bit
3. 第 8 行的迴圈會跑遍 `numsSize` 內的所有數字，當前比較的 `bit` 的出現數量會被紀錄，在 `c1` 會記錄範圍內數字的 `bit` 出現數量，而 `c2` 則是記錄 `nums` 裡數字的 `bit` 出現數量。
4. 有了兩者的出現數量，就可以用 `if (c1 < c2)` 判斷當前的 `bit` 是否為==出現次數過多==的 bit，把當前的 bit 加進去 `res` 內。
### 運用 GNU extension 改善程式
上述的程式碼的時間複雜度為 $O(nlogn)$，空間複雜度為 $O(1)$
- 時間複雜度為 $O(n)$，空間複雜度為 $O(n)$
宣告一條長度與 `numsSize` 相同的陣列去紀錄每個數字是否有出現過，缺點明顯，耗費記憶體空間
```cpp=
int findDuplicate(int *nums, int numsSize)
{
int* arr = malloc((numsSize+1) * sizeof(int));
for(int i=0; i<numsSize+1; ++i)
arr[i] = 0;
for(int i=0; i<numsSize; ++i){
if(!arr[nums[i]-1])
arr[nums[i]-1] = 1;
else
return nums[i];
}
return 0;
}
```
- 其他方法，正在思考 TODO
Sign in with Wallet
Connect another wallet