# 2020q3 Homework6 (quiz6)
contributed by < `jonec76` >
###### tags: `sysprog-2020`
> [作業說明](https://hackmd.io/@sysprog/r1z0WPWLD)
> [題目](https://hackmd.io/@sysprog/2020-quiz6)
## 開發環境
```shell
$ uname -a
Linux jonec76-Aspire-M7720 5.4.0-47-generic #51-Ubuntu SMP GNU/Linux
```
## 參考解答
D1=2
D2=1
ZZZ=1-i
## Q1
## Q2
- 解題想法
此題是要調整 ring buffer 頭跟尾的 index
```c=1
#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)
```
檢查目前的 index 是否還沒有達到 buffer size，如果還沒有達到這 size 就 +1，否則的話則依據 ring buffer 的特性，調整 START/END 的位置到 0。
至於為什麼 macro 裡頭會有下方的程式碼呢？
```c=1
do { ... } while (0)
```
查了 [stack overflow](https://stackoverflow.com/questions/257418/do-while-0-what-is-it-good-for) 中看到，在 `#define` 一個函式時，無法使用 `{}` 將該函式封起來，必須要透過 `while(0)` 的方法才行，若不封裝的話則有可能產生下方的問題，原本的程式碼如下
```c=1
#define FOO(x) { foo(x); bar(x); }
if (condition)
FOO(x)
else
...
```
若把 macro 展開之後將會得到以下的程式碼
```c=1
#define FOO(x) { foo(x); bar(x); }
if (condition)
foo(x);
bar(x);
else
...
```
此時就會發現有部分程式執行結果會有問題，就是因為沒有將函式封裝好。
## Q3
- 解題想法
A~D 的填空，是要在 list 新增一個值，題目是下方程式碼
```c=1
#define cons(x, y) (struct llist[]){{y, x}}
struct llist *list = cons(cons(cons(cons(NULL, A), B), C), D);
```
覺得這寫法很有趣，一步一步看 macro 如何應用在新增 list
```c=1
cons(cons(NULL, A), B)
```
在 `cons(NULL, A)` 對一個 `struct list []` 做初始化並且回傳一個 `struct list []` 的型態，是一個 pointer，這個 pointer 會傳到外層的 `cons` 變成該 `cons` 的 `next`。
所以說，最裡面的 `cons` 所回傳的 list 會在最後一個的位置（tail）。題目希望印出 `9547` 這樣的順序，所以 A 是最右邊尾巴的值 7，D 是最左邊頭的值 9，中間順序以此類推。
接著，看到 `sorted_insert` 題目，此函式是希望能夠邊插新的值，邊做排序，程式碼如下方。
```c=1
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;
}
```
此函式能夠分成兩個部分來看
1. `node->val` 比 `(*head)->val` 小
2. `node->val` 比 `(*head)->val` 大
在函式的下方 while loop 部分是處理 (2) 的部分。每次當有新的值進來時，都要從頭往尾巴跑過一次，透過比大小能夠找出此新的 value 該插入哪個位置。
至於 (1) 的部分，就是在上面 `if` 做處理，可以用下面的圖片表示
會進入 if 條件裡頭的 case，可以用下面的圖來表示
```graphviz
digraph linked_list{
rankdir=LR
node [shape=record];
h [label="{ <data> head | <ref> }"];
2 [ style=filled fillcolor=gray label="{ <data> 2| <ref> }"];
4 [ style=filled fillcolor=gray label="{ <data> 4 | <ref> }"];
6 [ style=filled fillcolor=gray label="{ <data> 6 | <ref> }"];
8 [ style=filled fillcolor=gray label="{ <data> 8 | <ref> }"];
h:ref:e->4:data:n
4:ref:g -> 6:data [arrowtail=dot, dir=both, tailclip=false];
6:ref:h -> 8:data [arrowtail=dot, dir=both, tailclip=false];
}
```
因為 `node->val` 比 `(*head)->val` 的值還小，所以要更改 `head` 的位址。步驟是
1. 將新的 `node` 的 `next` 指向目前 `head` 的位址
2. 把 `head` 改成 `node` 的位址
這個部分概念就跟 [lab0](https://hackmd.io/@jonec76/lab0-c) 的 `q_insert_head` 一樣，換成程式碼如下
```c=1
node->next = *head
*head = node
```
## Q4
- 解題想法
此題的做法蠻有趣的，是使用 bitwise 的方式來解。題目希望能夠找出，在一個給定範圍內，找出 list 裡頭重複的那個 element。看完程式碼後，覺得這題想法可以從離散數學提到的鴿籠原理去思考
1. nums.length == n + 1
2. 1 <= nums[i] <= n
上方的限制將會導致，`nums` 這個陣列中必重複一個數字。如何找出這個數呢？概念簡單來說，是將該 array 以及 range 內的值全部加起來，並讓 array 的總和減去 range 的總和就可以找出哪個值重複了。
看到下方程式碼
```c=1
const size_t log_2 = 8 * sizeof(int) - __builtin_clz(numsSize);
```
首先先找出 `log(numsSize)`，要找出 `log_2` 是因為要知道做 bitwise 的上限在哪邊。
```c=1
int bit = 1 << i; // i = 0~log_2
for (size_t k = 0; k < numsSize; k++) {
if (k & bit) // (A)
++c1;
if (nums[k] & bit) // (B)
++c2;
}
```
這個 for 迴圈的想法就是說，在 A 部分時，會計算出在 range 底下，index=k 的 bit 有多少個 1，同時在 B 部分，是計算出在所有 element，index=k 的 bit 有多少個 1。
根據上述推出來的鴿籠原理，若是 c1=c2 的話，表示這個重複的值轉成二進制後，在第 k 這個 bit 的值為 0。否則的話，就表示該 bit 的值為 1。
```c=1
if (c1 < c2)
res += bit;
```
若為 1 的話，就將該 bit 加到 res。等到跑完了 log_2 的範圍之後，就可以知道重複的值在哪幾個 bit 為 1，即可得到該數值。
Sign in with Wallet
Connect another wallet