# 2021q1 Homework2 (quiz2)
contributed by <` limaoxd `>
###### tags: `NCKU Linux Kernel 2021`
## 作業目標
- [ ] 測驗一
- [X] 重新回答
- [ ] 延伸問題
- [ ] 測驗二
- [x] 重新回答
- [ ] 延伸問題
- [ ] 測驗三
- [ ] 重新回答
- [ ] 延伸問題
- [ ] 測驗四
- [ ] 重新回答
- [ ] 延伸問題
## 測驗一
### list 基本結構
>基本上等於 lab0 的 queue
1. ++**list_ele_t**++
```graphviz
graph {
A [label="list_ele_t",color=red]
a [label="*prev"];
b [label="*next"];
A -- a
A -- b
}
```
由此可知,這是一個 ***doubly linked list***.
並且由 ++**list_add_tail**++ 即可得知,這是一個環狀的 ***linked_list***.
```graphviz
digraph list{
node [shape=record];
1 [label="1 (head)",color=red];
2 [label="2"];
3 [label="3 (tail)",color=blue];
1->2->3->1 [dir=both]
}
```
### 解釋答案
#### ++**get_middle**++
**程式碼:**
```cpp
static list_ele_t *get_middle(struct list_head *list) //求得中斷點
{
struct list_head *fast = list->next, *slow;
list_for_each (slow, list) {
if (COND1 || COND2) //判斷是否遍歷完(根據奇偶有不同條件)
break;
fast = fast->next->next;
}
return list_entry(TTT, list_ele_t, list);
}
```
那現在來讓我們開始模擬==龜兔賽跑==的形式吧~
> 小朋友也能學的資料結構 (?
>> 老師的小孩應該滿瘋天竺鼠車車?
>> (自己畫圖有沒有加分🤤)
上圖是有奇數個 ***node*** 的情況,
當~~天竺鼠~~ **fast** 到達 **tail** 後,為確保不會進入無限迴圈, **COND1** 應為
```cpp
fast->next == list // next = head
```
而~~傑尼龜~~ **slow** 理所當然的到了 **middle** .
再來考慮偶數的情況
>
這樣一來在偶數的情況下 **COND2** 是甚麼也不明自白了
```cpp
fast->next->next == list //判斷fast next->next是頭就好了
```
#### ++**list_cut_position**++
**程式碼:**
```cpp
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
struct list_head *head_from_first = head_from->next;
if (list_empty(head_from))
return;
if (head_from == node) {
INIT_LIST_HEAD(head_to);
return;
}
head_from->next = node->next;
head_from->next->prev = head_from;
head_to->prev = node;
node->next = head_to;
head_to->next = head_from_first;
head_to->next->prev = head_to;
}
```
由程式碼得知,要開始將list切開來,所以 **MMM** 會是 **middle**,而 **middle** 需要由 ++**get_middle**++ 函式做回傳.
但 ++**get_middle**++ 並沒有把 **list** 回傳,所以第4題的答案剩下了 **(e)** 選項了
```cpp
&get_middle(&q->list)->list
```
而 **TTT** 也很好理解,在怎麼選也不會選 **fast** , 所以答案為 = **slow**
:::warning
選擇題只是讓批改和課堂互動更便利，你應該設想「如果要我憑空撰寫程式碼，要怎麼做？」學生能考進成大，已經說明很會考試，但不代表能夠分析和創作，後者才是我在意的特質。
:notes: jserv
:::
### 改進並著手實作
>TODO
---
## **測驗二 power-of-two**
### 測試程式流程,推測程式碼原理
**程式如下:**
```c=
uint16_t func(uint16_t N) {
/* change all right side bits to 1 */
N |= N >> 1;
N |= N >> X;
N |= N >> Y;
N |= N >> Z;
return (N + 1) >> 1;
}
```
**func** 其目的在於尋求<= **N** 的2次方幕,
藉由測資為 21 (0000000000010101)
首先 **N |= N >> 1**,其 **N**則變成 00000000000011111
而 | 的位元運算特性的得知,只要右移的量不為負值,接下來 **N** 也不會改動了.
那麼,接下來看到**第 9 行**,便可得知,將11111 變成 100000,再右移一位,便可得到16 (10000)
那麼接下來要做的事情如法炮製，就是想辦法將==最高位以下的 `0` 補成 `1`==
所以我們就取極端值1000000000000000,
依樣的步驟,就會發現,1的數量變成了**2**倍多(1100000000000000),
只要讓變成兩倍總共做4次就能補完所有位元,
那麼只要每次將向右移量變成2倍,即可補完.
所以得知 **X** **Y** **Z** 分別為 2,4,8.
Sign in with Wallet
Connect another wallet