# 2021q1 Homework2 (quiz2)
contributed by < `fdfdd12345628` >

[題目](https://hackmd.io/@sysprog/ByHRgtofu)

## 測驗 1

1. COND1
先來看看原始碼

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
原始碼如下

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，參考程式碼如下：

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 。因此實作方式如下：

    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
參考以下原始碼

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);` 在一行內複製完畢。