# 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，即可得到該數值。