# 2020q3 Homework6 (quiz6)
contributed by < `zzzxxx00019` >
>[2020q3 第 6 週測驗題](https://hackmd.io/@sysprog/2020-quiz6)
## 測驗 1
### 題目：
BFloat16 的範例
* 4049Hex = 0 10000000 1001001 = 3.14062510 ≈ π
下列是個轉換程式:
```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;
}
```
對應的測試程式:
```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;
}
```
參考執行結果:
```
3.140625=40490000
3.140625=40490000
1.200000=3f99999a
1.203125=3f9a0000
2.310000=4013d70a
2.312500=40140000
3.460000=405d70a4
3.453125=405d0000
5.630000=40b428f6
5.625000=40b40000
```
請補完程式碼。
### 原理：
```cpp=2
float y = x;
int *py = (int *) &y;
unsigned int exp, man;
exp = *py & 0x7F800000u;
man = *py & 0x007FFFFFu;
```
* 將浮點數 `x` 以 `int` 方式，表達每個 `bit` 的數值
* 透過對 `0x7F800000u` 做 `and` 運算，可以得到 `fraction` 的 `bit`
* 透過對 `0x007FFFFFu` 做 `and` 運算，可以得到 `exponent` 的 `bit`
```cpp=7
if (!exp && !man) /* zero */
return x;
if (exp == 0x7F800000u) /* infinity or NaN */
return x;
```
* 預先檢查不同 `case` ，做出不同的配套措施， `zero` 、 `infinity` 、 `NaN` 都直接回傳 `x`
|value|sign|exponent|fraction|
| - | - | - | - |
| 0 | |00000000|00..00 |
| inf | |11111111|00..00 |
| NaN | |11111111| !=0 |
```cpp=12
/* Normalized number. round to nearest */
float r = x;
int *pr = (int *) &r;
*pr &= BB1;
r /= 256;
y = x + r;
```
* 利用 `*pr &= 0xff800000` 取出 `sign` 與 `exp` 的部分
* 原本的 $x$ 可表達為 $2^k\times1.fraction$ ，經過 `15` 、 `16` 行的運算後， $r=2^{k-8}$
* $y=x+r$ 就可寫成 $2^k\times1.fracion+2^{k-8}$ ，整理後得到 $2^k\times(1.fraction+2^{-8})$ ，相當於對 `fraction` 的部分，在第 `8 bit` 加上 `1` ，意即對分數的第 `8 bit` 無條件進位
```cpp=19
*py &= BB2
```
* 最後再保留下 `bfloat16` 的 `sign` 、 `exp` 、 `fraction` ，透過 `*py &= 0xffff0000` 達到此目的
---
## 測驗 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)` 巨集：
參考 [multi-line macro: do/while(0) vs scope block](https://stackoverflow.com/questions/1067226/c-multi-line-macro-do-while0-vs-scope-block) 中討論區的解釋
#### 比較以下兩種不同方法的差別：
* 第一種，使用 `do/while(0) loop`
```cpp
#define FOO \
do { \
do_stuff_here \
do_more_stuff \
} while (0)
```
* 第二種，使用 `basic block`
```cpp
#define FOO \
{ \
do_stuff_here \
do_more_stuff \
}
```
#### 解釋差別：
* 考慮到以下的 `code`
```cpp
if (<condition>)
foo(a);
else
bar(a);
```
* 若將 `foo(a)` 以 `macro` 的方式取代
```cpp
if (<condition>)
CALL_FUNCS(a);
else
bar(a);
```
如果使用的巨集是 `basic block` ，會導致 `compile` 失敗，原因是當執行完 `if` 的 `true branch` 後，碰上執行完 `macro` 後的分號 「 ; 」 ，導致判斷式終結，然而 `else` 無法單獨存在，而出現 `compile error` ，而要修正此問題的方法，就是呼叫 macro 後，後面別加上分號，修正後如下：
```cpp
if (<condition>)
CALL_FUNCS(a)
else
bar(a);
```
但這種方法顯得比較彆扭，比較理想的方法是確保 `macro` 可以展開為 `regular statement` ，而非上面的 `compound statement` ，因此透過 `do{ ... }while(0)` 這樣的寫法，可以維持原本 `coding` 的習慣，不會出現 `compile error` ，在使用 `macro` 看起來也較一致，注意到的是 `...while(0)` 後面不可加上分號，否則就會出現像上述那樣的 `compound statement` 問題
* 將 `macro` 以 `do/while(0) loop` 的方式包覆內容程式
```cpp
#define CALL_FUNCS(x) \
do { \
func1(x); \
func2(x); \
func3(x); \
} while (0)
```
在條件式使用 `macro` 就可以不用刻意去注意分號的問題
```cpp
if (<condition>)
CALL_FUNCS(a);
else
bar(a);
```
### 原理：
* `Ring Buffer` 實作一個環形的 `buffer` ，透過下圖解釋其結構：
初始狀態，假設給定 `buffer size` 為 `6` 的 `ring buffer` ， `start` 與 `end` 都指向第 `0` 格的位置
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0> | | | | |" shape=record]
start -> ring_buffer:0
end -> ring_buffer:0
}
```
每次新增資料時，都寫入到 `end` 的位置，而 `end` 再往後退一格，例如將 `1` 寫入， `end` 則從第一格退向第二格
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0> 1|<1> | | | |" shape=record]
start -> ring_buffer:0
end -> ring_buffer:1
}
```
當 `buffer` 飽和的狀態下，會出現 `start` 與 `end` 同時都指向同一格的狀況
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0>1|2|3|4|5|6" shape=record]
start -> ring_buffer:0
end -> ring_buffer:0
}
```
為了解決 `buffer` 在飽和狀態，在 end 寫入資料，會導致 `end` 退到 `start` 後面的狀況，因此預先將 `start` 往後退一格
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0>1|<1>2|3|4|5|6" shape=record]
start -> ring_buffer:1
end -> ring_buffer:0
}
```
因此當下一筆資料寫入飽和的 `ring buffer` 時，將會捨去 `ring` 中存放最久的 `element` ，以寫入 `7` 為例，將原本的 `1` 給取代，因又再次飽和， `start` 往後退一格
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0>7|<1>2|<2>3|4|5|6" shape=record]
start -> ring_buffer:2
end -> ring_buffer:1
}
```
而取出資料時，從 `start` 開始讀出，並將 `start` 往後退一格
```graphviz
digraph {
start [shape = plaintext]
end [shape = plaintext]
ring_buffer [label = "<0>7|<1>2|<2>|<3>4|5|6" shape=record]
start -> ring_buffer:3
end -> ring_buffer:1
}
```
* 再從 `ringbuf_write` 與 `ringbuf_read` 兩個角度去看 `ring` 的整個實作流程：
#### `ringbuf_write` 程式碼
```cpp
#define ringbuf_write(BUF, ELEMENT) \
do { \
ringbuf_write_peek(BUF) = ELEMENT; \
ringbuf_write_skip(BUF); \
} while (0)
```
* 呼叫 `ringbuf_write_peek()` ，將 `ELEMENT` 寫入 `BUF` 的 `end`
```cpp
#define ringbuf_write_peek(BUF) (BUF)->elements[(BUF)->end]
```
* 新增 `ELEMENT` 後，呼叫 `ringbuf_write_skip()` ，調整當前 `end` 的位置
* `NEXT_END_INDEX()` ： 調整 `(BUF)->end` 位置，如果 `end` 位置尚未走到 `buf` 的 `size` ，代表 `end` 仍有向後退的空間，故 `end` 向後退 `1` 格，即 `(BUF)->end + 1` ，若 `end` 已走到 `buffer` 的最尾端，則回到起始點 `0` 的地方，如此達到 `ring` 的效果
* `is_ringbuf_empty(BUF)` ： 原本是檢查 `buffer` 是否為 `empty` ，但若在新增完 `element` 後， `end` 與 `start` 同一位置，代表 `buffer` 目前為飽和的狀態，則必須對目前 `(BUF)->start` 做相對應的處理
* `NEXT_START_INDEX()` ： 調整 `(BUF)->start` 位置，如果 `start` 位置尚未走到 `buf` 的 `size` ，代表 `start` 仍有向後退的空間， 故 `(BUF)->start + 1` ，若 `start` 已走到尾端，則回到 `BUF` 的初始位置 `0`
* 呼叫 `NEXT_START_INDEX()` ，處理 `buffer` 在飽和狀態時， `start` 與 `end` 都指向起始位置的問題，將 start 往後退一格，即捨去掉 `buffer` 中，存放最久的 `element`
```cpp
#define NEXT_END_INDEX(BUF) (((BUF)->end != (BUF)->size) ? ((BUF)->end + RB2) : 0)
```
```cpp
#define NEXT_START_INDEX(BUF) \
(((BUF)->start != (BUF)->size) ? ((BUF)->start + RB1) : 0)
```
```cpp
#define is_ringbuf_empty(BUF) ((BUF)->end == (BUF)->start)
```
```cpp
#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)
```
#### `ringbuf_read` 程式碼
```cpp
#define ringbuf_read(BUF, ELEMENT) \
do { \
ELEMENT = ringbuf_read_peek(BUF); \
ringbuf_read_skip(BUF); \
} while (0)
```
* 呼叫 `ringbuf_read_peek()` ，將 `ring buffer` 中， `start` 指向的 `element` 取出
```cpp
#define ringbuf_read_peek(BUF) (BUF)->elements[(BUF)->start]
```
* 再透過 `ringbuf_read_skip()` ，調整取出 `buffer` 元件後， `start` 的位置
```cpp
#define ringbuf_read_skip(BUF) (BUF)->start = NEXT_START_INDEX(BUF);
```
---
## 測驗 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) {
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;
}
```
其執行結果為:
```
9547
4579
```
請補完程式碼，使程式碼和執行結果相匹配。
### 原理：
```cpp=4
#define cons(x, y) (struct llist[]){{y, x}}
```
* 參考 [你所不知道的C語言：技巧篇](https://hackmd.io/@sysprog/c-trick#inode) 文章內容
* 使用 `con(x, y)` 可以得到 `node->val = y` 且 `node->next = x` 的節點
* 因此將 `cons(cons(cons(cons(NULL, A), B), C), D)` 展開可以得到以下的 `List`
```graphviz
digraph
{
rankdir=LR ;
node [shape = record] ;
D->C->B->A->NULL
}
```
```cpp=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;
}
```
* `Linked list` 經排列後，將 `node` 插入到相對應的位置
* 透過 `pointer-to-pointer` 直接對 `main` 的 `head` 取值，因此 `**head` 為 `main head` 實際的位址
* 當 `list` 沒有 `node` 或是 `head->value >= node->value` 時， `head` 將由 `node` 取代
* `SS1 : node->next = *head` ，將 `node` 的 `next` 接上原本的 `head`
* `SS2 : *head = node` ，再將 `node` 設為目前的 `head`
* 否則依序尋訪節點，找到適當的位置，將新的節點插入
```cpp=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;
}
```
* `sort` 的方法是依序尋訪每個節點，並透過 `sorted_insert` 建立一個 `sort list`
* 當 `current != NULL` ，就將 `current node` 透過 `sorted_insert` 加入 `sorted list`
* 最後再將 `head` 接上排序好的 `sorted list`
```cpp=39
struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
```
* 若要使 `list` 以 `9547` 的順序排列，則 `A ~ D` 應依序填入 `7` 、 `4` 、 `5` 、 `9`
---
## 測驗 4
### 題目：
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;
}
```
```
Example 1:
Input: nums = [1,3,4,2,2]
Output: 2
Example 2:
Input: nums = [3,1,3,4,2]
Output: 3
Example 3:
Input: nums = [1,1]
Output: 1
```
### 原理：
* 題目測資有一個很重要的規定：陣列長度為 $n$ ，數值的範圍是 $1$ 到 $n-1$ ，因此陣列中，不會有數值為 `0` 的測資出現，即重複的值必定取代 `0` 而出現 `1` 次以上
* 若把陣列中，每個 `bit` 拆開比對，取代 `0` 的就是重複出現的數字，因此在只重複出現一次的可能時，重複出現的那個數字在該值 `bit` 為 `1` 的位置時，會比 `0` 多出 `1 bit`
* 考慮到重複出現的次數不只 `1` 次，代表重複出現的數字，在該值 `bit 1` 的位置，其 `bit 1` 的數量必定大於原本數值為 `0 ~ n-1` 的陣列，因此 `CCC=c1<c2`
假設 `numsSize = 3：` ， `c1` 在計算下表中，每個 `bit` 為 `1` 的數量
| val | bit 1 | bit 0 |
| -- | -- | -- |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
|bit 1| 1 | 1 |
若 `nums = [1,1,2]：` ， `c2` 在計算下表中，每個 `bit` 為 `1` 的數量
| val | bit 1 | bit 0 |
| -- | -- | -- |
| 1 | 0 | 1 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
|bit 1| 1 | 2 |
因為下表的 `1` 取代了上表中的 `0` ，因此在下表在 `bit 0` 的位置，數量會大於上表，透過此方法找出每個 `bit` 多出來的數值，就可以知道哪個數字重複，此方法在 leetcode 上的表現結果如下：
### 延伸問題：
* 實作不同的程式碼
* 以桶子排序法的方式，透過 `bucket[i]` 計算 `i` 值出現的次數
* 當 `num[i] > 1` ，代表 `i` 即為重複的值
* 也可用 `bool` 對 `bucket[i]` 中每個位置設立 `flag` ，當 `flag = 1` 且有值填入，即重複
```cpp=
int findDuplicate(int *nums, int numsSize) {
int bucket[numsSize] ;
memset(bucket, 0, sizeof(bucket)) ;
for (int i=0 ; i<numsSize ; i++){
bucket[ nums[i] ] += 1 ;
if ( bucket[ nums[i] ] > 1 ) return nums[i] ;
}
return 0 ;
}
```
```cpp=
int findDuplicate(int *nums, int numsSize) {
bool bucket[numsSize] ;
memset(bucket, 0, sizeof(bucket)) ;
for (int i=0 ; i<numsSize ; i++){
if ( !bucket[ nums[i] ] ) bucket[ nums[i] ] ^= 1 ;
else return nums[i] ;
}
return 0 ;
}
```
Sign in with Wallet
Connect another wallet