# 2021q1 Homework2 (quiz2)
contributed by < `fdfdd12345628` >
[題目](https://hackmd.io/@sysprog/ByHRgtofu)
## 測驗 1
1. COND1
先來看看原始碼
```clike=
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);
}
```
由於它用在`list_merge_sort`裡面的方式,再加上他的函式名稱,因此可以判斷它的用處是取得 list 中間位置。
而方式就是用兩個指標掃過 list ,其中一個是另一個的兩倍速。當兩倍速的掃完整個 list 後,另一個就會在一半的位置。
因此 COND1 就是 ` fast->next == list` ,也就是快速的指標到達 list 結尾。
2. COND2
承上題,因為快速的指標一次跳兩個,因此當達到 list 結尾時也要判斷 `fast->next->next == list`
3. MMM
原始碼如下
```clike=
static inline void list_cut_position(struct list_head *head_to,
struct list_head *head_from,
struct list_head *node)
{
...
list_cut_position(&left.list, &q->list, MMM);
...
```
可以看到 `MMM` 的型態是 `list_head *`,而且要傳入 `get_middle` 所做出來的結果。而 `get_middle` 的輸入與回傳型態如下:
```
static list_ele_t *get_middle(struct list_head *list);
```
因此要先取出 `q` 的 `list` 傳入 `get_middle` ,接著將回傳的 `list_ele_t` 也取出 `list` ,因此 `MMM` 就是 `&get_middle(&q->list)->list` 。
4. TTT
承第一、二題,因為慢速指標會在迴圈結束時到達一半的位置,因此要回傳的是 `list_entry(TTT, list_ele_t, list);`
## 測驗 2
此段城市要回傳小於或等於 N 的 power-of-2,參考程式碼如下:
```clike=
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;
}
```
假定 $N = 10101_2 = 21_{10}$,那麼 func(21) 要得到 16。也就是說,要找到他的 most significant 的 1 ,並且將其他的 bit 變成 0 。其中有一個辦法是將 most significant 的 1 之後的 bit 全部變成 1
$$
00010101 => 00011111
$$
並且將其加一後,再往右移一個 bit
$$
00011111+1=00100000
$$
$$
00100000 => 00010000
$$
而我們可以將第一個1的bit逐一複製到之後的bit,不過這樣子太慢。如果用指數的方式讓已經複製過的地方也一同複製,可以快速讓 most significant 的 1 之後的 bit 全部變成 1 。因此實作方式如下:
```clike=
N |= N >> 1;
N |= N >> 2;
N |= N >> 4;
N |= N >> 8;
```
因此就算 N 只有一個 bit 是 1 ,他也可以讓 N 的該 bit 後都是 1。不過如果 N 是第一個 bit 就是 1 的話,就可能會 overflow ,下列以 `int8_t` 為例:
$$
10000000 => 11000000
$$
$$
11000000 => 11110000
$$
$$
11110000 => 11111111
$$
不過因為 1 是 int 型態,因此 `(N + 1)` 實際上回傳值也是 int ,所以在 N 是 `uint16_t` 的情況下是不會 overflow 的。
因此 X, Y, Z 分別為 2, 4, 8
## 測驗三
1. RRR
參考以下原始碼
```clike=
void bitcpy(void *_dest, /* Address of the buffer to write to */
size_t _write, /* Bit offset to start writing to */
const void *_src, /* Address of the buffer to read from */
size_t _read, /* Bit offset to start reading from */
size_t count)
{
size_t read_lhs = _read & 7;
size_t read_rhs = 8 - read_lhs;
...
if (read_lhs > 0) {
RRR;
if (bitsize > read_rhs)
data |= (*source >> read_rhs);
}
...
```
當 `read_lhs > 0` 時,代表他不是對齊一個 byte 讀取,因此要將 data 位移 read_lhs 個 bit ,也就是 `data <<= read_lhs` 。
如果 data 位移 read_lhs 個 bit 時,會存取到下一個 byte 時,就要將下個 byte 的資料補上。所以當 `bitsize > read_rhs` 時,就是存取到下一個 byte 時,就要 `data |= (*source >> read_rhs);` 來補上下一個 byte 的內容。
2. DDD
當複製的 bit 在一個 byte 內,則可以將兩個 mask 合在一起,也就是 `mask |= write_mask[write_lhs + bitsize]` 。這樣子就可以直接執行 `*dest++ = (original & mask) | (data >> write_lhs);` 在一行內複製完畢。