# 2021q1 Homework2 (quiz2) contributed by < `ngokchaoho` > > [第 2 週測驗題](https://hackmd.io/@sysprog/linux2021-quiz2) ## 系統環境 * Ubuntu Linux 20.04.1 LTS ## 測驗 1 解釋程式碼運作原理，指出改進空間並著手實作 以下這段函式目標如名字所示，是要拿到中間的節點。留意 list_head 是由 linux/list.h 提供的，利用 list_head 這個結構體，我們可以打造一個雙向鏈結串列，因此 `struct list_head *list` 如下圖 11-1 所示的，沒有 data，作用是連接頭和尾。 ```cpp static list_ele_t *get_middle(struct list_head *list) { struct list_head *fast = list->next, *slow; list_for_each (slow, list) { if (fast->next == list || fast->next->next == list) break; fast = fast->next->next; } return list_entry(slow, list_ele_t, list); } ``` ![](https://i.imgur.com/CaWMYAc.png) :::warning 修正下方「兩格」這樣不精準的用語 :notes: jserv ::: :::info 已修正 :notes: ngokchaoho ::: 然後 fast 每次都會前往下一節點所指向的再下一個節點，slow 則通過 `list_for_each` 前往當前指點指向的下一個節點。因此 fast 遍歷雙向鏈結串列的速度會是 slow 的兩倍。 ```cpp /** * list_for_each - iterate over list nodes * @node: list_head pointer used as iterator * @head: pointer to the head of the list */ #define list_for_each(node, head) \ for (node = (head)->next; node != (head); node = node->next) ``` 當 fast 到達尾時（在乎於是奇數還是偶數，有可能是倒數第一個或倒數第二個，所以需要兩個條件去確定是否已抵達開頭），slow 恰好在中間。留意到目前為止所説到的遍歷都是透過 list_head 進行。因此，`get_middle` 原本用 list_entry 回傳 slow 所在（即中間）的用户自定義的結構體變數位址。 最後用 `list_cut_position` 把原本的 queue 分成兩半。留意因為我們回傳的是用户自定義的結構體變數位址 `list_ele_t`，因此需要大費周章地`&get_middle(&q->list)->list)` 拿回對應的 `list_head` 部分。 ```cpp void list_merge_sort(queue_t *q) { if (list_is_singular(&q->list)) return; queue_t left; struct list_head sorted; INIT_LIST_HEAD(&left.list); list_cut_position(&left.list, &q->list, &get_middle(&q->list)->list); list_merge_sort(&left); list_merge_sort(q); list_merge(&left.list, &q->list, &sorted); INIT_LIST_HEAD(&q->list); list_splice_tail(&sorted, &q->list); } ``` 我建議更改成：`get_middle` 直接回傳 list_head。 ```cpp static struct list_head *get_middle(struct list_head *list) { struct list_head *fast = list->next, *slow; list_for_each (slow, list) { if (fast->next == list || fast->next->next == list) break; fast = fast->next->next; } return slow; } ``` ```cpp void list_merge_sort(queue_t *q) { if (list_is_singular(&q->list)) return; queue_t left; struct list_head sorted; INIT_LIST_HEAD(&left.list); list_cut_position(&left.list, &q->list, get_middle(&q->list)); list_merge_sort(&left); list_merge_sort(q); list_merge(&left.list, &q->list, &sorted); INIT_LIST_HEAD(&q->list); list_splice_tail(&sorted, &q->list); } ``` ## 測驗 2 解釋程式碼運作原理 ```cpp= uint16_t func(uint16_t N) { /* change all right side bits to 1 */ N |= N >> 1; N |= N >> 2; N |= N >> 4; N |= N >> 8; return (N + 1) >> 1; } ``` N 是一個無號整數 ，此函式回傳小於或等於 N 的 power-of-2 如果將 N 以 binary 的形式寫出，則只要將 N 目前的 MSB 設為 1 （已經是1），其餘的位元設為零則會達到 power-of-2 二的冪。 ```shell (gdb) set $g=0b1010 (gdb) set $g|=$g>>1 (gdb) p /t $g $16 = 1111 (gdb) set $g=($g+1)>>1 (gdb) p /t $g $17 = 1000 (gdb) ptype $g type = int ``` 具體的做法是先將 MSB 右方（默認 big-endian）所有位元變為1，然後透過+1，使得 MSB 左方位元變為1，其他為零，然後在透過右移將1放到原本的 MSB。留意，即使 1111，1111，1111，1111 +1 也不會有 over-flow 的問題，因為對 [integer constant](https://en.cppreference.com/w/cpp/language/integer_literal) 1 （屬於 int）做加運算會將 16 位無號整數亦 promote 為 int，運算的結果亦為 int。 >6.3.1.8 Usual arithmetic conversions >Many operators that expect operands of arithmetic type cause conversions and yield result types in a similar way. The purpose is to determine a common real type for the operands and result. For the specified operands, each operand is converted, without change of type domain, to a type whose corresponding real type is the common real type. Unless explicitly stated otherwise, the common real type is also the corresponding real type of the result, whose type domain is the type domain of the operands if they are the same, and complex otherwise. 接下來，會説明為何 3-6 行程式會有 `/* change all right side bits to 1 */` 的效果，舉例説明： - 原本的 N 0000 0000 001? ???? - 對 N 右移1位 >>1，得到 0000 0000 0001 ???? - 最後通過 |= operator bitwise inclusive OR 運算，得到 0000 0000 0011 ???? 如此一來，我們由只能確定 MSB 上是 1，變成能確定 2 個 1。 依次類推，`N |= N >> 2;`會確定 4 個 1。然後，`N |= N >> 4;` 確定 8 個 1，最後 `N |= N >> 8;` 確定 16 個 1。