2025q1 Homework2 (quiz1+2)

contributed by < LambertWSJ >

quiz1

題目連結

測驗 1

按照 list_insert_before 的描述，將 item 插入到串列 l 的 before 前，給定的實做使用指標的指標 p，經過 for 迴圈完後，dereference p 並指派為 item，表示將節點換成 item，item 還需要將下個節點指向 before，因為 item 可能是從別的串列來的，而不是單一節點，因此 item->next 指向的是原串列的節點，而不是串列 l 的 before。

*p = before;
item->next = before;

for 迴圈的目的是要從串列 l 找出 before，因此 p 要指向 l 的開頭，並透過 &(address of) 運算子，依據 C99 6.5.3.1:3

The unary & operator yields the address of its operand. If the operand has type ‘‘type’’,
the result has type ‘‘pointer to type’’

轉換成指標的指標，才會和 p 是同型別，迴圈的終止條件是對 p 做 dereference 取得節點的位址和 before 做比較，不是 before 的話就更新 p 到下個節點。離開迴圈後 p 會指向 before，在由上個段落所描述的操作，就能將 item 插入到 before 之前。

for(p = &l->head; *p != before; p = &(*p)->next)

實做 Merge sort

先實做簡單的遞迴版 Merge sort，函式宣告如下

list_item_t *list_merge_sort(list_item_t *head);

傳入 list 的 head 會較容易撰寫，不用另外處理不同型別的問題，專注在節點上即可。Merge Sort 拆分為分割和合併兩個階段，分割的策略使用快慢指標，遞迴地處理串列的左半邊和右半邊，將左半邊的串列分割為單一節點，單一節點是排序好的，可以和其他排序好的子串列或單一節點合併，當左半邊都集中合併完之後，會將同一處理過程換到右半邊操作，當左右半邊的子串列都排序完後，再合併成排序好的串列。

list_item_t *list_merge_sort(list_item_t *head) {
    if (!head || !head->next)
        return head;

    list_item_t *slow = head, *fast;
    for (fast = head->next; fast && fast->next; fast = fast->next->next)
        slow = slow->next;

    list_item_t *mid = slow->next;
    slow->next = NULL;
    list_item_t *left = list_merge_sort(head);
    list_item_t *right = list_merge_sort(mid);
    return merge_two_lists(left, right);
}

合併函式 merge_two_lists 應用指標的指標，這樣就不需要額外配置記憶體或是 dummy 節點來當 head，只需要指標 list 作為合併完的串列開頭，再用指標的指標 indir 指向 list，當 indir 解參考就能存取到 list，把要合併的節點指派給 list，串列的開頭就有了，要更新下個節點的話只要將 indir 指向到下一個節點即可。

static list_item_t *merge_two_lists(list_item_t *l1, list_item_t *l2) {
    list_item_t *list = NULL, **indir = &list;
    list_item_t **node;
    for (node = NULL; l1 && l2; *node = (*node)->next) {
        node = l1->value < l2->value ? &l1 : &l2;
        *indir = *node;
        indir = &(*indir)->next;
    }
    /* ... */
}

node 的用途是指向下個要合併的節點，比較 l1 和 l2 的值後，紀錄下個要合併的節點，依據 C99 規格書 6.5.15 的註腳

A conditional expression does not yield an lvalue

&(l1->value < l2->value ? l1 : l2) 這樣寫沒辦法讓 address of(&) 取得地址，因為三元表達式回傳的是 value 而非帶有地址的 lvaue，雖然不能夠回傳 lvalue，但可以回傳已經是地址的 value，即 &l1 或 &l2。

有了下個要合併的節點，需要對 node 透過解參考才能存取到它，並指派給 indir 合併，合併完的節點同樣也是透過解參考來達成 *node = (*node)->next，就會將已經合併完的節點更新到下一個。

當迴圈到達終止條件 l1 && l2 離開時，表示其中一個串列還沒合併完，需要將其合併到 indir 上，才算是完成。這裡可以應用一個小技巧。依據 C99 7.18.1.4:1, 使用 uintptr_t 將串列的地址轉為無號整數來操作

The following type designates an unsigned integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
uintptr_t

l1 和 l2 其中一個是合併完的串列，地址就會是 NULL, NULL 的地址是零，零和其他數值就 or 操作，都會是原來的數值，所以將兩個串列的地址做 or 得到的地址就是還沒合併完的串列，再轉形成 list_item_t * 並指派給 *indir 就完成合併了

list_item_t *merge_two_lists(list_item_t *l1, list_item_t *l2) {
    /* ... */
    *indir = (list_item_t *) ((uintptr_t) l1 | (uintptr_t) l2);
    return list;
}

測驗 2

測驗 3

quiz2

題目連結

測驗 1

測驗 2

clz2

題目給定分治法的 clz，參數 x 和 c 分別為 32 位元無號輸入數值和 leading zero 的位置，為方便說明，leading zero 簡寫為 LZ。

因為是拆成 upper 和 lower 各 16 bit 來做，等最後 2 bit 再來判斷位置，而 LZ 只會在其中一個，依據最後 2 bit 作為判斷條件，16 向右位移 3 就會剩下 2 bit。

c 和判斷 upper/lower 的長度，如下表，acc 表示從 c 等於 0 累加 16 >> c

c	upper/lower	acc(16 >> c)
0	16	16
1	8	24
2	4	28
3	2	30

unsigned clz2(uint32_t x, int c) {
    /* ... */
    if (c == 3)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}

雖然看到 mask 和 magic 已經知道 c 很可能是 3，但是這樣子判斷欠缺合理性，mask 和 magic 再多塞幾個數值在陣列裡面的話，就被騙到了。

因為每次都要少一半長度的判斷，下次 lower 的遞迴則是 (16 >> (c)) + clz2(lower, c + 1)，遞迴函式執行到終止條件時會逐步返回，過程中累加 16 >> c 到 30。

若 LZ 在 upper，則當 c == 3 會剩下兩個 bit，可以用來推測 magic，此時的 upper 是 x 的第 30 和 31 個 bit，

$x_{[31:30]}$ 表示 x 的第 30 到 31 個 bit，用 2 進位表示數值，由小到大整理成下表，LZ 也代表 magic 的數值

$x_{[31:30]}$ or $x_{[1:0]}$	LZ
${00}_2$	2
${01}_2$	1
${10}_2$	0
${11}_2$	0

有了 magic 可以判斷 KKKK 應為 2。

從每次要從 upper 或 lower 判斷 LZ 位置來看，mask 的 GGGG 應為 14，這樣在 c 為 3 時，判斷的長度才會是 2

static const int mask[] = {0, 8, 12, GGGG};
unsigned clz2(uint32_t x, int c) {
    /* ... */
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    /* ... */
}

sqrti

ToDo：本文說明可能有誤，釐清詞彙中
帶入和代入
除和除以

實做完 clz 後，嘗試實做基於 2 進位的 digit-by-digit method 的整數平方根，研讀講義和 Wiki 後，可能是篇幅問題所以部份公式沒有推導，直接給出來，藉此機會來練習推導看看。

假設

$N^2$ 可以用二進位系統取得逼近解

$$N^2=(a_n+a_{n-1}+\cdots +a_1+a_0{)}^2$$

其中

$a_m$ 可能是

$2^m$ 或是

$0$，計算

$2^n$ 到

$2^0$ 並累加起來，會得到平方根

$P_m$

$$P_m=a_n+a_{n-1}+\cdots +a_m$$

要找出

$a_m$ 是

$2^m$ 或

$0$，先將

$P_m$ 改寫成另一種等價的形式

$$P_m=P_{m+1}+a_m$$

過去看到數學公式通常都是下一項等於前一項做運算得出來，這裡的

$P_m$ 則是相反，用下一項

$P_{m+1}$ 運算得出來，把

$P_m$ 帶數字展開來就知道為什麼了，令

$m=4,n=7$

$$\begin{array}{rl}& P_4=a7+a6+a5+a4\\ & P_5=a7+a6+a5\end{array}$$

可以看出

$P_m$ 和

$P_{m+1}$ 少了一個

$a_m$。

如果

$P_m^2$ 沒有超過

$N^2$，則

$a_m=2^m$，表示

$a_m$ 是包含在平方和

$P_m$ 裡面的係數，不會因為加上

$a_m$ 就超過

$N^2$，反之如果超過的話，就不屬於

$P_m$，

$a_m=0$

$$a_m=\{\begin{array}{ll}{2}^m,& \text{if }{P}_m^2\le N^2\\ 0,& otherwise\end{array}$$

找出每一項

$a_m$ 並累加，就可以得到整數平方根

$P_m$。

為避免每一次計算

$a_m$ 都要對

$P_m$ 做平方，可以儲存兩數之差

$X_m=N^2-P_m^2$，並逐步更新

$X_m$，為此要推導下一項

$X_{m+1}$

$$X_{m+1}=N^2-P_{m+1}^2$$

$P_{m+1}^2$ 可以展開成

$(P_m-a_m{)}^2$ 並帶入如差平方的公式

$$\begin{array}{rl}{X}_{m+1}& =N^2-(P_m-a_m{)}^2\\ & =N^2-(P_m^2-2P_m{a}_m+a_m^2)\\ & =N^2-P_m^2+2P_m{a}_m-a_m^2\end{array}$$

其中

$X_m=N^2-P_m^2$ 以及

$P_m=P_{m+1}+a_m$，代入展開後的式子

$$\begin{array}{rl}{X}_{m+1}& =N^2-P_m^2+2P_m{a}_m-a_m^2\\ & =X_m+2(P_{m+1}+a_m)a_m-a_m^2\\ & =X_m+2P_{m+1}{a}_m+2a_m^2-a_m^2\\ & =X_m+2P_{m+1}{a}_m+a_m^2\end{array}$$

得出

$X_{m+1}=X_m+2P_{m+1}{a}_m+a_m^2$。

令

$Y_m=2P_{m+1}{a}_m+a_m^2$ 得

$X_m=X_{m+1}-Y_m$，探討

$a_m$ 不為零時的情況，並將

$Y_m$ 拆成

$c_m$ 和

$d_m$

$$\begin{array}{rl}{c}_m& =2P_{m+1}{a}_m=P_{m+1}{2}^{m+1}\\ d_m& =(2^m{)}^2\end{array}$$

$$Y_m=\{\begin{array}{ll}{c}_m+d_m& \text{if }{a}_m=2^m\\ 0& \text{if }{a}_m=0\end{array}$$

$c_m$ 和

$d_m$ 的更新如下

$$c_{m-1}=P_m{2}^m=(P_{m+1}+a_m)2^m=P_{m+1}{2}^m+a_m{2}^m$$

其中

$a_m$ 可能是

$0$ 或是

$2^m$，如果

$a_m=2^m$，帶入

$c_{m-1}$

$$c_{m-1}=P_{m+1}{a}^m+a_m^2=\frac{c_m}{2}+d_m$$
若

$a_m=0$ 代入

$c_{m-1}$

$$\begin{array}{rl}{c}_{m-1}& =(P_{m+1}+a_m)2^m\\ & =P_{m+1}{2}^m\\ & =\frac{c_m}{2}\end{array}$$

故得知更新

$c_m$ 和

$d_m$ 的公式如下

$$\begin{array}{rl}{c}_{m-1}& =\{\begin{array}{ll}\frac{c_m}{2}+d_m& \text{if }{a}_m=2^m\\ \frac{c_m}{2}& \text{if }{a}_m=0\end{array}\\ d_{m-1}& =(2^{m-1}{)}^2=\frac{d_m}{4}\end{array}$$

公式都推導出來後，回頭看程式碼，先回答為什麼要取出 msb 而且還要是 4 的冪?

$P_m$ 是

$a_n$ 累加到

$a_m$，

$a_m$ 不確定是多少，有幾個，但至少會有一個，那就是最高項

$a_n$，這也是為什麼

$P_m$ 要從

$a_n$ 開始累加到

$a_m$。

初始值

$P_n=a_n=2^n$,

$P_n$ 要滿足

$P_n^2\le N^2$, 則

$P_n^2=(2^n{)}^2=4^n$，因此初始值必須是最接近

$N$ 的 4 的冪。

uint64_t sqrti(uint64_t x) {
    /* ... */
    int shift = (total_bits - 1 - clz64(x)) & -2;
    m = 1ULL << shift;
    /* ... */
}

有了

$a_n$ 就能按照更新公式來迭代求得逼近解

$P_m$ 剩下的

$a_m$。將

$a_n$ 代入並計算初始

$Y_m=c_m+d_m$

$$\begin{array}{rl}{Y}_m& =c_m+d_m\\ & =P_{m+1}{2}^{m+1}+(2^m{)}^2\\ & =(P_m-2^n)2^{n+1}+(2^n{)}^2\end{array}$$
初始值

$P_m=P_n=a_n$ 代回上式

$$\begin{array}{rl}{Y}_m& =(P_m-2^n)2^{n+1}+(2^n{)}^2\\ & =(2^n-2^n)2^{n+1}+(2^n{)}^2\\ c_m& =0,d_m=a_n^2\end{array}$$
因為

$c_m=0$，

$d_m$ 可在迴圈中算出來，所以一開始 y 才設為 0，y 也可以一開始就設為 m 但是迴圈要另外處理。

uint64_t sqrti(uint64_t x) {
    uint64_t m, y = 0; /* y = c_m */
    int shift = (total_bits - 1 - clz64(x)) & -2;
    m = 1ULL << shift; /* m = d_m = a_n^2 */
    /* ... */
}

初始的

$Y_m$ 算好之後，就可以準備更新

$c_m$ 和

$d_m$ 了，更新公式如下

$$\begin{array}{rl}{c}_{m-1}& =\{\begin{array}{ll}\frac{c_m}{2}+d_m& \text{if }{a}_m=2^m\\ \frac{c_m}{2}& \text{if }{a}_m=0\end{array}\\ d_{m-1}& =(2^{m-1}{)}^2=\frac{d_m}{4}\end{array}$$
無論

$a_m$ 是否為零，

$c_m$ 都要除 2，

$d_m$ 每次都要除 4，若

$a_m$ 存在，則

$c_{m-1}$ 要再加上

$d_m$，而

$d_m$ 每一輪都要除 4

$a_m$ 是否存在，要藉由

$X_{m+1}\ge Y_m$ 判斷，如果存在的話，

$X_m$ 也要更新，公式如下

$$X_m=X_{m+1}-Y_m$$

這裡看上去不直覺，為什麼又是用下一項 (

$X_{m+1}$) 來更新？

嘗試推導

$X_{m+1}$ 來解釋

$$X_{m+1}=N^2-P_{m+1}^2=N^2-(P_m-a_m{)}^2$$
因為是從最高位來計算，令

$m=n$，會得出

$X_{m+1}=N^2$

$$X_{m+1}=N^2-(a_n-a_n{)}^2=N^2$$

當

$m=n$ 時，

$X_{m+1}$ 剛剛好是

$N^2$，此外

$m$ 所代表的意義是位數，因此當

$X_{m+1}\ge Y_m$ 時，更新

$X_m$ 的時候是用前一次高位的

$X_{m+1}$ 減去

$Y_m$。

uint64_t sqrti(uint64_t x) {
    /* ... */
    while (m) {
        uint64_t b = y + m; /* Y_m = c_m + d_m */
        y >>= 1;
        if (x >= b) { /* check a_m exist     */
            x -= b;   /* X_m = X_{m-1} - Y_m */
            y += m;   /* c_{m-1} += d_m      */
        }
        m >>= 2;
    }
    return y;
}

測驗 3