2025q1 Homework2 (quiz1+2)

contributed by < thwuedwin >

第 1 週測驗一

程式碼運作原理分析

這個測驗主要考察對指標操作的熟練度。目標是實作 list_insert_before 函式，它的功能是在鏈結串列中找到指定的節點 before，並將 item 插入到它的前面。
該函式會接收以下參數：

l：指向鏈結串列的指標
before：目標節點
item：要插入的節點

實作方式是從 l->head 開始遍歷鏈結串列，直到找到 before，然後將 item 插入至其前方。

不使用間接指標的程式碼

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

這個版本直接使用 p 作為普通指標，在找到 before 之前，持續向後移動 p，最後修改 p->next 來完成插入。

使用間接指標的程式碼

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

這個版本改用指向指標的指標 p，直接追蹤 next 指標的位置，這樣在插入 item 時，不需要額外處理 p->next，程式碼更加簡潔。

題目	答案
AAAA	`&l->head`
BBBB	`before`
CCCC	`&(*p)->next`
DDDD	`item->next`

優雅之處

不使用間接指標的版本雖然可行，但需要處理 p->next，而使用間接指標的版本則巧妙地利用 p 直接指向 next 指標的位置，使得：

迴圈條件 *p != before 更直覺，不需要額外比較 next
*p = item 直接修改指標，不需要額外處理 p->next

這樣的設計讓程式碼更加簡潔，減少了變數存取的間接層級，提高了可讀性和可維護性。

實作：合併排序




































void merge_sort(list_t *l) {
    if (list_empty(l) || list_is_singular(l))
        return;

    list_t left, right;
    list_item_t *slow, *fast, *before;
    slow = fast = l->head;
    while (fast && fast->next) {
        before = slow;
        slow = slow->next;
        fast = fast->next->next;
    }
    left.head = l->head;
    right.head = slow;
    before->next = NULL;
    
    merge_sort(&right);
    merge_sort(&left);

    // merge
    list_item_t *head, *l1, *l2;
    list_item_t **p = &head;
    l1 = left.head;
    l2 = right.head;
    for (; l1 && l2; p = &(*p)->next) {
        if (l1->value <= l2->value) {
            *p = l1;
            l1 = l1->next;
        } else {
            *p = l2;
            l2 = l2->next;
        }
    }
    *p = (list_item_t *)((uintptr_t)l1 | (uintptr_t)l2);
    l->head = head;
}

尋找中間節點（第 5～15 行）
使用快慢指標來找到鏈結串列的中間節點。
由於此實作使用的是單向鏈結串列，無法直接回溯，因此我們額外使用變數 before 記錄 slow 前一個節點，以便切斷鏈結，將其拆分成左右兩個子串列。
示意圖如下：
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
遞迴排序子串列（第 17～18 行）
將拆分後的 left 和 right 子串列遞迴地進行合併排序。
合併兩個排序好的子串列（第 21～35 行）
- 利用間接指標來避免對特殊情況的額外處理，例如首節點的變更。

此次實作也善用了我在第 2 週測驗一學習到的想法，用堆疊的區域變數來管理暫存的節點。

第 1 週測驗二

程式碼運作原理分析

根據函式名稱 remove_free_tree，我推測它的目的是尋找可用空間並將其從 free tree 中移除。然而，我一開始無法理解 find_free_tree 的具體功能，尤其是它的回傳型態竟然是 block_t **，這點讓我感到困惑。

在仔細閱讀程式碼後，我發現 remove_free_tree 的主要操作是更新變數 node_ptr，並根據 *node_ptr 子節點的數量，選擇不同的方式來更新它。此外，並且該函式的初始化方式是 find_free_tree(root, target)。基於以上觀察，我推測這個函式的作用如下：

find_free_tree(root, target) 在 free tree 中搜尋 target，並回傳指向 target 之親代節點指標的指標。例如，若 node->l == target 為真，則回傳 &node->l。該回傳值由 block_t **node_ptr 接收，這樣一來，只要更新 node_ptr，便能直接修改親帶節點的指向。這種設計相當聰明且優雅。如示意圖：
Image Not Showing Possible Reasons
- The image was uploaded to a note which you don't have access to
- The note which the image was originally uploaded to has been deleted
Learn More →
根據 target 子樹的結構，決定用哪個節點來取代 target：
- 若 target 有兩個子節點，則選擇左子樹最右側的節點來取代 target。
- 若 target 僅有一個子節點，則讓該子節點直接取代 target。
- 若 target 沒有子節點，則僅需將其移除。
在移除 target 之前，將其子節點指標設為 NULL，避免產生錯誤的參照。

尋找左子樹最右節點的程式碼

block_t **pred_ptr = &(*node_ptr)->l;
while ((*pred_ptr)->r)
    pred_ptr = &(*pred_ptr)->r;

題目	答案
EEEE	`(*pred_ptr)->r`
FFFF	`&(*pred_ptr)->r`

實作： Custom memory allocators

目標是實作一個以 free tree 管理可用空間的記憶體分配器，目前實作尚未完成，以下是 ftalloc.h 程式碼：

























#define BRK_SIZE 135168
typedef struct block {
    size_t size;
    struct block *l, *r;
} block_t;

typedef struct memory {
    void *addr;
    block_t block;
} memory_t;

block_t *root = NULL;

void init_free_tree();
void brk_free_tree(size_t size);
void free_free_tree();

block_t **find_free_tree(block_t **root, block_t *target);
block_t *find_predecessor_free_tree(block_t **root, block_t *node);
void remove_free_tree(block_t **root, block_t *target);
void insert_free_tree(block_t **root, block_t *target);


void *ftalloc(size_t size);
void ftfree(void *p);

ftalloc 和 ftfree 函式是預計提供給使用者呼叫的，功能應該與 malloc 和 free 相同。
第 7 - 9 行的函式負責管理可動態配置出的記憶體：
- 在使用此記憶體空間配置器前，必需先呼叫 init_free_tree。init_free_tree 會使用 malloc 預先配置預設為 BRK_SIZE 大小的空間，作為初始可動態配置的記憶體空間。該區塊會由 free tree 管理。
- 若需要動態配置的空間超出 free tree 所管理的範圍，則呼叫 brk_free_tree 來增加可配置的空間並將新增的空間加入 free tree，預設擴展大小為BRK_SIZE。
- 程式結束後需呼叫 free_free_tree 來釋放由 init_free_tree 和 brk_free_tree 分配的記憶體區塊。
第 18 - 21 行的函式負責新增和移除 free tree 節點：
- 在使用者呼叫 ftalloc 時，remove_free_tree 會在 free tree 中尋找適當的空間，將該區塊從 free tree 移除，並維護 free tree 的結構與完整性。詳細見上方程式碼分析。
- 在使用者呼叫 ftfree 時，insert_free_tree 會將釋放的空間重新加入 free tree，恢復其可用狀態。

困難點

按照題目的指示，應該要預先分配好不同大小的區塊，以增加空間區域性（spatial locality）。但這會增加記憶體管理所需的開銷。在 64-bit 系統中，每個指標變數的大小為 8 位元組，memory_t 結構至少佔 28 位元組，若每個 4 位元組的空間都由一個 memory_t 來管理的成本太高了。
解決方案：
- 我目前的思路是將 memory_t 管理的最小單位設定為一個 page。每個 page 內會包含多個小區塊，並且使用額外的標籤來標明每個 page 所儲存空間的特定大小及其內部的 free list。對於每個 page 內的 free list，我打算使用更高效且成本較低的資料結構，例如 bit map，來儲存每個區塊的使用狀態。
另一個需要考量的問題是記憶體對齊問題（memory alignment）。目前我還沒有確定具體的解決方案，但這部分應該需要參考現有的記憶體配置器，了解如何處理對齊需求。一般來說，記憶體分配器會確保分配的區塊大小能夠符合系統的對齊要求。

第 1 週測驗三

程式碼運作原理分析

此測驗快速排序法的方式雖然不是使用遞迴實作，仍然是採用了分治的想法。

把串列的第一個節點當作樞紐（pivot），走訪串列所有節點，將大於樞紐值的節點加入 right 串列，反之加入 'left' 串列。最終形成三個子串列，分別由 left、pivot 和 right 所指向。
依序檢查 right、pivot 和 left 指向的串列是否需要排序，此演算法會先優先處理最右邊的串列。

流程比較複雜不好簡單解釋，直接參考程式碼：

while (i >= 0) {
        struct list_head *L = begin[i], 
                         *R = list_tail(begin[i]);
        if (L != R) {
            /* Distribute each node into the 
             * appropriate list: left, pivot,
             * or right, based on its value.  
             */
            begin[i] = left;
            begin[i + 1] = pivot;
            begin[i + 2] = right;
            left = right = NULL;
            i += 2;
        } else {
            if (L) {
                L->next = result;
                result = L;
            }
            i--;
        }

第 3 行的 if(L != R) 判斷該串列是否包含兩個以上的元素，若是，則需排序。分類後會產生三個子串列，因此做 i += 2，代表下一輪處理最後新增的串列。而else 對應到串列僅有一個元素，表示已經排序完成，直接合併到 result 內。

為何 max_level 的設值為

$2 n$ ？

int max_level = 2 * n;
struct list_head *begin[max_level];

我思考流程是，考慮當串列大小為

n

，且原先已排序（升序）時，每次選擇樞紐值都會選到當前最小的元素。因此：

left 為空
pivot 僅包含該最小值
right 包含剩餘的
$n - 1$ 個元素

由於該實作不是穩定排序，下一次迭代會選擇 right 的最大值作為新樞紐，接著又選擇最小值，如此交替進行。結果是：

right 為空
下一輪會將當前最大值合併至 result
這個方法不會產生
$2 n$ 個串列，最只會產生
$n$ 個。於是我改變思路，我希望每次選樞紐都選到最小的樞紐。觀察到在將原始串列搬移到 left 或 right 時是有尾端插入，可以利用這個特性建構串列。舉實際例子，假設有一串列順序為 [1 3 5 7 8 6 4 2]，則排序過程為

[] [1] [2 4 6 8 7 5 3]
[] [1] [] [2] [3 5 7 8 6 4]
[] [1] [] [2] [] [3] [4 6 8 7 5]
…
依此類推，最終就會產生
$2 n$ 個串列。

題目	答案
GGGG	`head->prev=prev`
HHHH	`list_entry(pivot,node_t,list)->value`
IIII	`list_entry(n,node_t,list)->value`
JJJJ	`pivot`
KKKK	`right`

研讀〈A comparative study of linked list sorting algorithms〉

本文探討六種常見排序演算法的效率，並分析其時間複雜度與實際執行效能。下方表格皆來自〈A comparative study of linked list sorting algorithms〉
大 O 表示法與實際效率
雖然在理論上，排序演算法的效率通常以

O (f (n))

表示，但由於常數因子的影響，只有在

n

足夠大時，

O (n^{2})

的演算法才會比

O (n \log n)

的演算法顯著低效。本研究的實驗範圍為

n \geq 100

，因此可從結果觀察不同演算法在實務上的表現。若在

n ， 100

的區間可能會有不同的結果。
從下表可見，在時間複雜度為

O (n \log n)

的排序演算法中，二元樹排序法（Tree Sort）的效率優於快速排序法（Qsort）及合併排序法（Msort）。
截圖 2025-03-16 16.24.40

常數因子分析

根據表格 1 和表格 2 的數據，可透過理論時間複雜度擬合出各演算法的常數，結果整理於表格 3。
截圖 2025-03-16 16.31.28
表格 3 中的 ratio 欄位代表當

n \leq 1000

與

n > 1000

時，對應的時間常數比值：

比值大於 1：表示該演算法在較小的
$n$ 下效率較佳，此實驗中複雜度為
$O (n^{2})$ 的演算法屬於這類。
比值小於 1：表示該演算法在較大的
$n$ 下效率較佳，此實驗中複雜度為
$O (n \log n)$ 的演算法屬於這類。

這些常數也可用來評估不同演算法之間的效率差異，提供量化的效能對照。

此外，值得注意的是，本研究的測試方法是對同一組輸入進行多次實驗後取平均值。換句話說，輸入串列的排列方式可能僅限於少數幾種固定模式，這可能導致比較結果的不公平性。例如，雖然合併排序、快速排序和二元樹排序在平均時間複雜度皆為

O (n \log n)

，但快速排序與二元樹排序在最差情況下可能達到

O (n^{2})

，而合併排序的最差時間複雜度仍維持在

O (n \log n)

。然而，本文並未深入探討這些最差情況下的差異。此外，該研究僅以執行效率作為評估標準，並未考量演算法是否為穩定排序法（Stable Sort）或原地演算法（In-place Algorithm），這些因素在實務應用上可能同樣重要。

實作：雙向鏈結串列排序演算法

根據前述的實驗結果，二元樹排序（Tree Sort）在效率上表現較佳，因此我選擇實作此演算法。
二元樹排序的核心概念是：

建立一棵二元搜尋樹（BST, Binary Search Tree），將鏈結串列中的節點依序插入二元搜尋樹。
使用深度優先搜尋（DFS, Depth-First Search） 走訪 BST，並依序將節點還原為排序後的鏈結串列。

插入二元搜尋樹的平均時間複雜度為

O (\log n)

，最差情況下則為

O (n)

。由於共需插入

n

個節點，整體排序的平均時間複雜度為

O (n \log n)

，而最差情況下可能達到

O (n^{2})

。
樹狀結構如示意圖：

實作
排序函式 treesort 是主流程，此外，我實作了 bst_insert 和 bst_traverse 兩個輔助函式來處理二元搜尋樹的建立與遍歷。

主排序函式：treesort

treesort 會遍歷鏈結串列，將節點依序從原串列刪除後插入二元搜尋樹，最後透過 bst_traverse 將二元搜尋樹轉回排序後的鏈結串列。

static void treesort(struct list_head *head)
{
    struct list_head *node, *safe, *root = NULL;
    list_for_each_safe (node, safe, head) {
        list_del(node);
        node->prev = NULL;
        node->next = NULL;
        bst_insert(&root, node);
    }
    bst_traverse(root, head);
}

插入函式：bst_insert

bst_insert 會將給定的節點插入二元搜尋樹。透過遞迴尋找適當的插入位置，並使用間接指標來處理二元搜尋樹的根節點與子樹的連結關係。
if (root_element->value > node_element->value) 這個條件確保二元搜尋樹遵循穩定排序的特性，。

void bst_insert (struct list_head **root, struct list_head *node)
{
    if (!*root) {
        *root = node;
        return;
    }

    element_t *root_element, *node_element;
    root_element = list_entry(*root, element_t, list);
    node_element = list_entry(node, element_t, list);
    if (root_element->value > node_element->value)
        bst_insert(&(*root)->prev, node);
    else
        bst_insert(&(*root)->next, node);
}

遍歷函式：bst_traverse

bst_traverse 會 以中序遍歷（In-Order Traversal） 的方式走訪二元搜尋樹，並將最小的節點依序插回鏈結串列，達到排序的效果。

void bst_traverse (struct list_head *root, struct list_head *head)
{
    struct list_head *work;
    if (root) {
        bst_traverse(root->prev, head);
        work = root->next;
        INIT_LIST_HEAD(root);

        //printf("%d ", list_entry(root, element_t, list) ->value);
        list_add_tail(root, head);
        bst_traverse(work, head);
    }
}

第 2 週測驗一

程式碼運作原理分析

此測驗實作的是遞迴版本的快速排序，採用鏈結串列的方式進行排序。

選取一個節點作為樞紐（pivot），走訪每個節點，將小於樞紐值的節點加入 list_less，其餘則加入 list_greater。
遞迴地對 list_less 和 list_greater 進行排序。
最終合併 list_less、pivot 和 list_greater，得到完整的排序結果。

題目	答案
AAAA	`list_first_entry`
BBBB	`list_del`
CCCC	`list_move_tail`
DDDD	`list_add`
EEEE	`list_splice`
FFFF	`list_splice_tail`

學習心得

在實作時，我經常猶豫應該使用區域變數還是動態配置記憶體來宣告 struct 變數。例如，我原本可能會寫出以下動態配置的版本：

{
    struct list_head *list_less, *list_greater;
    list_less = malloc(sizeof(stuct list_head));
    list_greater = malloc(sizeof(stuct list_head));
    // ...
}

這種做法需要額外處理記憶體釋放 (free)，並且因為變數的生命週期變長，必須在額外的地方確保值的正確性，這可能反而會降低程式的可讀性和安全性。

相比之下，若改為區域變數，則可以利用遞迴的堆疊行為自動釋放記憶體，提升一致性與安全性：

{
    struct list_head list_less, list_greater;

    INIT_LIST_HEAD(&list_less);
    INIT_LIST_HEAD(&list_greater);

    // ...

    list_quicksort(&list_less);
    list_quicksort(&list_greater);
}

這樣的設計方式讓變數的生命週期受到更好的控制，避免了手動管理記憶體可能帶來的錯誤。

穩定排序（stable sorting）分析

快速排序的穩定性主要取決於節點加入 list_less 和 list_greater 的方式。

由於樞紐選擇最左側節點，因此與樞紐值相等的節點應該放在 list_greater，確保相同數值的元素仍維持原本的相對順序。
關鍵點：加入串列時必須從尾端插入，如果從前端插入，原本的順序會被反轉。因此，應使用 list_move_tail 來保持排序的穩定性：

list_for_each_entry_safe (item, is, head, list) {
    if (cmpint(&item->i, &pivot->i) < 0)
        list_move_tail(&item->list, &list_less);
    else
        list_move_tail(&item->list, &list_greater);
}

這樣的做法確保了排序的穩定性，即原本相同數值的節點在排序後仍維持其相對順序。

實作：改善 `random_shuffle_array`

實作：整合 `qtest` 並使用 perf 進行效能分析

整合 qtest

修改 qtest.c
- 在 console_init 函式內新增

ADD_COMMAND(qsort, "Sort queue in ascending/descening order implemented by quicksort", "");

- 實作 `do_qsort` 函式，並呼叫對應的快速排序函式 `q_qsort`

修改 queue.c
- 實作 q_qsort 函式

void q_qsort(struct list_head *head, bool descend)
{
    list_quicksort(head);
    if (descend)
        q_reverse(head);
}

以 perf 進行效能分析
我實作了一個函式來讀取輸入檔案，該檔案包含 1024 個長度為 8 的字串。測試函式會將這些字串依序插入鏈結串列，並根據命令列參數選擇相應的排序方法：

sort：對應原本實作的合併排序（Merge Sort）。
qsort：對應此次新增的快速排序（Quicksort）。

實驗環境

$ cat /etc/os-release
PRETTY_NAME="Ubuntu 24.04.1 LTS"
NAME="Ubuntu"
VERSION_ID="24.04"
VERSION="24.04.1 LTS (Noble Numbat)"
VERSION_CODENAME=noble
ID=ubuntu
ID_LIKE=debian
HOME_URL="https://www.ubuntu.com/"
SUPPORT_URL="https://help.ubuntu.com/"
BUG_REPORT_URL="https://bugs.launchpad.net/ubuntu/"
PRIVACY_POLICY_URL="https://www.ubuntu.com/legal/terms-and-policies/privacy-policy"
UBUNTU_CODENAME=noble
LOGO=ubuntu-logo
$ lscpu
Architecture:             x86_64
  CPU op-mode(s):         32-bit, 64-bit
  Address sizes:          46 bits physical, 48 bits virtual
  Byte Order:             Little Endian
CPU(s):                   20
  On-line CPU(s) list:    0-19
Vendor ID:                GenuineIntel
  Model name:             12th Gen Intel(R) Core(TM) i7-12700
    CPU family:           6
    Model:                151
    Thread(s) per core:   2
    Core(s) per socket:   12
    Socket(s):            1
    Stepping:             2
    CPU(s) scaling MHz:   25%
    CPU max MHz:          4900.0000
    CPU min MHz:          800.0000
    BogoMIPS:             4224.00
    Flags:                fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx p
                          dpe1gb rdtscp lm constant_tsc art arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf tsc_known_freq pni pclm
                          ulqdq dtes64 monitor ds_cpl vmx smx est tm2 ssse3 sdbg fma cx16 xtpr pdcm sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes x
                          save avx f16c rdrand lahf_lm abm 3dnowprefetch cpuid_fault epb ssbd ibrs ibpb stibp ibrs_enhanced tpr_shadow flexpriority ept vpid e
                          pt_ad fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid rdseed adx smap clflushopt clwb intel_pt sha_ni xsaveopt xsavec xgetbv1 x
                          saves split_lock_detect user_shstk avx_vnni dtherm ida arat pln pts hwp hwp_notify hwp_act_window hwp_epp hwp_pkg_req hfi vnmi umip
                          pku ospke waitpkg gfni vaes vpclmulqdq rdpid movdiri movdir64b fsrm md_clear serialize pconfig arch_lbr ibt flush_l1d arch_capabilit
                          ies
Virtualization features:
  Virtualization:         VT-x
Caches (sum of all):
  L1d:                    512 KiB (12 instances)
  L1i:                    512 KiB (12 instances)
  L2:                     12 MiB (9 instances)
  L3:                     25 MiB (1 instance)
NUMA:
  NUMA node(s):           1
  NUMA node0 CPU(s):      0-19
Vulnerabilities:
  Gather data sampling:   Not affected
  Itlb multihit:          Not affected
  L1tf:                   Not affected
  Mds:                    Not affected
  Meltdown:               Not affected
  Mmio stale data:        Not affected
  Reg file data sampling: Mitigation; Clear Register File
  Retbleed:               Not affected
  Spec rstack overflow:   Not affected
  Spec store bypass:      Mitigation; Speculative Store Bypass disabled via prctl
  Spectre v1:             Mitigation; usercopy/swapgs barriers and __user pointer sanitization
  Spectre v2:             Mitigation; Enhanced / Automatic IBRS; IBPB conditional; RSB filling; PBRSB-eIBRS SW sequence; BHI BHI_DIS_S
  Srbds:                  Not affected
  Tsx async abort:        Not affected
$ gcc --version
gcc (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
Copyright (C) 2023 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

執行結果如下：

$ sudo perf stat -e cycles,instructions ./test sort
 Performance counter stats for './test sort':

     <not counted>      cpu_atom/cycles/                                                        (0.00%)
         1,918,165      cpu_core/cycles/
     <not counted>      cpu_atom/instructions/                                                  (0.00%)
         2,850,215      cpu_core/instructions/           #    1.49  insn per cycle

       0.000717136 seconds time elapsed

       0.000675000 seconds user
       0.000000000 seconds sys

$ sudo perf stat -e cycles,instructions ./test qsort
 Performance counter stats for './test qsort':

     <not counted>      cpu_atom/cycles/                                                        (0.00%)
         1,648,884      cpu_core/cycles/
     <not counted>      cpu_atom/instructions/                                                  (0.00%)
         2,862,565      cpu_core/instructions/           #    1.74  insn per cycle

       0.000584501 seconds time elapsed

       0.000000000 seconds user
       0.000609000 seconds sys

目前尚未詳細分析兩者的效能差異，後續將進一步探討如何進行合理的比較，並補充更詳細的測試與分析結果。

第 2 週測驗二

程式碼運作原理分析

此測驗涉及 clz（counting leading zero）和整數開平方根 sqrti 的實作。

`clz` 分析

clz 的目標是計算數值的 leading zeros 的數量。實作方法是將數值拆分為上半部（upper）與下半部（lower），並根據以下邏輯進行遞迴計算：
• 若 upper 為零，則遞迴計算 lower 的 leading zero，並加上 upper 佔據的位數。
• 若 upper 不為零，則遞迴計算 upper 的 leading zero。

思路
由於遞迴的流程較難直觀理解，因此我先找出初始條件與遞迴結束條件。

if (c == JJJJ) 條件下並未進行遞迴呼叫，推測這是遞迴終止的條件。
c + 1 會在每次遞迴時遞增，當 c == 3 時應該要終止，否則可能導致超出陣列範圍存取錯誤。

if (c == JJJJ)
    return upper ? magic[upper] : KKKK + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);

根據巨集定義 #define clz32(x) clz2(x, 0)，推測 x 為目標數值，而 c 則記錄目前處理的階段。

c == 0 時，處理 32 位元數值
c == 1 時，處理 16 位元數值
c == 2 時，處理 8 位元數值
c == 3 時，處理 4 位元數值

逐行分析 clz2















static const int mask[] = {0, 8, 12, GGGG};
static const int magic[] = {HHHH, 1, 0, IIII};

unsigned clz2(uint32_t x, int c)
{
    if (!x && !c)
        return 32;

    uint32_t upper = (x >> (16 >> c));
    uint32_t lower = (x & (0xFFFF >> mask[c]));
    if (c == JJJJ)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

第 9 行：upper 取得 x 的上半部位元。
第 10 行：lower 取得 x 的下半部位元，其中 0xFFFF 是 16 位的遮罩，前 16 位為 0，後 16 位為 1，透過 mask[c] 決定要保留的位數。當 c 為 3 時，應該要留下末兩位元，因此 mask[3] 為 14。
當 c == 3（處理 4 位元）時，magic[] 儲存 2 位元對應的 leading zero 數量，因此：
- magic[] = {2, 1, 0, 0}
- 當 upper != 0，回傳 magic[upper]
- 當 upper == 0，leading zero 為 upper 的 2 位元加上 magic[lower]

題目	答案
GGGG	14
HHHH	2
IIII	0
JJJJ	3
KKKK	2
LLLL	1

`sqrti` 分析

參考：從 √2 的存在談開平方根的快速運算
理論分析
設

N

為正整數，目標是求出

N

的平方根值（以整數表示）。

\begin{aligned} N & = (b_{n} \times 2^{n} + b_{n - 1} \times 2^{n - 1} + . . . + b_{0} \times 2^{0})^{2} \\ = (a_{n} + a_{n - 1} + . . . + a_{0})^{2} \end{aligned}

其中，

b_{i} = 0

1, i = 1, 2, . . ., n

、

a_{i} = b_{i} \times 2^{i}

。
假設最高位為非零元素為第 k 位，亦即，

b_{i} = 0,

for

i > k

。我們有

a_{k} = 2^{k} > \sum_{i = 0}^{k - 1} a_{i} = 2^{k} - 1

又對於任何

x \geq 2

，

x^{2} \geq 2 x

。於是對於第一個

a_{k}^{2} \leq N

，必須把

b_{k}

設成

1

。否則就算把第 k 位以下都設成

1

，對於估計

\sqrt{N}

還是太小。我認為這是一個不嚴謹但相對直觀的解釋，搭配實作可以很好的幫助理解。
因此演算法可以以這個方法實作

從最高位
$n$ 開始檢查，直到找到第一個
$a_{k}^{2} \leq N$ ，則把
$b_{k}$ 設成
$1$ 。
接者，若
${(a_{k} + a_{k - 1})}^{2} \leq N$ ，則把
$b_{k - 1}$ 設為
$1$ ，反之設為
$0$ 。設
$P_{m} = \sum_{i = m + 1}^{n} a_{i}$ ，因為
$a_{i}$ 在第
$k$ 位以上都是
$0$ ，也可以簡化為
$P_{m} = \sum_{i = m + 1}^{k} a_{i}$ ，以現階段為例就是
$P_{k - 2} = \sum_{i = k - 1}^{k} a_{i} = a_{k} + a_{k - 1}$ 。
計算
$P_{k - 3}^{2} = {(a_{k} + a_{k - 1} + a_{k - 2})}^{2}$ ，並和
$N$ 比較，若
$P_{k - 3}^{2} \leq N$ ，則把
$b_{k - 2}$ 設為
$1$ ，反之設為
$0$ 。
以此類推直到計算到
$P_{0}$ ，最終結果
$\sqrt{N}$ 可以用
$(b_{k} b_{k - 1} . . . b_{0})_{2}$ 來估計。

定義

X_{m} = N - P_{m}^{2}

為實際值和逼近值的誤差，其中

Y_{m} = (2 P_{m + 1} + a_{m}) a_{m}

，可以縮減計算過程。
補

Y_{m}

來源

$X_{m} = N - P_{m}^{2} = X_{m + 1} - Y_{m}$
$Y_{m} = P_{m}^{2} - P_{m + 1}^{2} = (2 P_{m + 1} + a_{m}) a_{m}$

實作

uint64_t sqrti(uint64_t x)
{
    uint64_t m, y = 0;
    if (x <= 1)
        return x;

    int total_bits = 64;
    int shift = (total_bits - 1 - clz64(x)) & ~1;
    m = 1ULL << shift;

    while (m) {
        uint64_t b = y + m;
        y >>= 1;
        if (x >= b) {
            x -= b;
            y += m;
        }
        m >>= 2;
    }
    return y;
}

此程式碼可以直接對應到上述理論。m = 1ULL << shift 是將初始的

P_{n}

設定為

a_{n}

。若 y 記錄

P_{m}

，b = y + m為

P_{m - 1}

。不斷重複計算直到

P_{0}

。

題目	答案
MMMM	`~1`
NNNN	`1`
PPPP	`2`

實作：開平方根向上取整
$⌈ \sqrt{N} ⌉$

我一開始打算往數學的方式思考。正如前面提到的，此實作會比較

P_{m}^{2}

和

N

的大小，若小於

N

則加入。但如果要做向上取整就比較困難，向上取整代表勢必需要

P_{m}^{2} \geq N

，但很難知道到底需要大多少。於是我認為這個方向行不通。
我改成從實作著眼，若非完全平方數則需要加

1

，完全平方數則不需要。我的思路轉為去思考完全平方數和非完全平方數的差別。從理論思考，我猜測在迴圈結束的時候，若為完全平方數 x 應該要為

0

。於是我做了初步的實驗，我將

1

到

100

帶入，確認函式正確並且檢視函式結束時的 x 值。發現結果和我猜測的一樣：

x: 1, N: 2, sqrt(N): 1
x: 2, N: 3, sqrt(N): 1
x: 0, N: 4, sqrt(N): 2
x: 1, N: 5, sqrt(N): 2
x: 2, N: 6, sqrt(N): 2
x: 3, N: 7, sqrt(N): 2
x: 4, N: 8, sqrt(N): 2
x: 0, N: 9, sqrt(N): 3
x: 1, N: 10, sqrt(N): 3
x: 2, N: 11, sqrt(N): 3
x: 3, N: 12, sqrt(N): 3
x: 4, N: 13, sqrt(N): 3
x: 5, N: 14, sqrt(N): 3
x: 6, N: 15, sqrt(N): 3
x: 0, N: 16, sqrt(N): 4
x: 1, N: 17, sqrt(N): 4
x: 2, N: 18, sqrt(N): 4

但我認為在接近無號整數最大值附近會出問題於是我在 sqrti 的最後加了一行 assert(x == 0)，並只傳入完全平方數。測試函式如下：

for (int i = 0; i < 65536; ++i) {
    sqrti(i*i)
}

但是 assert 報錯了，我目前測試到

2^{1} 5

都沒有問題，還沒找到最小會報錯的數字，原因要進一步分析。至少確定在

N < 2^{3} 0

要實作

⌈ \sqrt{N} ⌉

僅需要在 sqrti 函式的最後加上：

if (x != 0)
    ++y;

實作：不依賴除法的浮點數開平方根 `sqrtf`

實作：藉由查表的平方根運算

第 2 週測驗三

此測驗涉及雜湊表（hash table）的實作，並在發生雜湊碰撞（hash collision）時，將碰撞的兩個值用鏈結串列的方式串接起來。以下是程式碼和示意圖：
hlist

struct list_head {
	struct list_head *next, *prev;
};

struct hlist_head {
	struct hlist_node *first;
};

struct hlist_node {
	struct hlist_node *next, **pprev;
};

從程式碼中可以看出，雜湊表使用的鏈結串列與一般的雙向鏈結串列稍有不同，主要有以下兩點差異：

節省空間：雜湊表的鏈結串列不應該頻繁需要遍歷，也不需要快速存取尾節點。因此將首節點指向前一個元素的指標 pprev 省略，可以節省空間。因為雜湊表在建立時會創建大量的 hlist_head，其中有一部分可能完全不會使用到。
簡化刪除操作：pprev 是指向前一個節點 next 屬性的指標，這使得在刪除節點時更加方便。

Two Sum 實作
此測驗關於 LeetCode Two Sum。目標是高效率（O(N)）的尋找兩個數字，使它們的和為指定數字 n。為了達到這個目標，會構建一個雜湊表 ht。當現在搜尋的數字為 k 時，會檢查 ht[k] 是否存在。如果不存在，則建立 ht[n-k]；若存在，則表示找到所求的組合，並從儲存的資料中取出。
因此，資料結構如下：

typedef struct {
    int bits;
    struct hlist_head *ht;
} map_t;

struct hash_key {
    int key;
    void *data;
    struct hlist_node node;
};

其中 key 是

n - k

的雜湊值，data 儲存相關資料（本題為索引值）。

各個函式的運作分析

map_init：這個函式會動態配置出 map_t 結構的變數 map，並根據指定的雜湊位元數動態配置出雜湊表的首節點，管理在 map 內。
map_add：這個函式將傳入的 key 和 data 加入雜湊表。會先檢查這個 key 是否已經在雜湊表中；若不存在，則會動態配置出一個新的 hlist_node 空間，並管理在 map 中。
map_deinit：這個函式會遍歷整個雜湊表並釋放 map_init 和 map_add 所配置的記憶體。

題目	答案
AAAA	`map->bits`
BBBB	`map->bits`
CCCC	`first->pprev`
DDDD	`n->pprev`
EEEE	`n->pprev`

2025q1 Homework2 (quiz1+2)

第 1 週測驗一

程式碼運作原理分析

實作：合併排序

第 1 週測驗二

程式碼運作原理分析

實作： Custom memory allocators

第 1 週測驗三

程式碼運作原理分析

研讀〈A comparative study of linked list sorting algorithms〉

實作：雙向鏈結串列排序演算法

第 2 週測驗一

程式碼運作原理分析

穩定排序（stable sorting）分析

實作：改善 random_shuffle_array

實作：整合 qtest 並使用 perf 進行效能分析

第 2 週測驗二

程式碼運作原理分析

clz 分析

sqrti 分析

實作：開平方根向上取整 ⌈N⌉

實作：不依賴除法的浮點數開平方根 sqrtf

實作：藉由查表的平方根運算

第 2 週測驗三

Read more

2025q1 Homework1 (lab0)

2025q1 Homework1 (ideas)

實作：改善 `random_shuffle_array`

實作：整合 `qtest` 並使用 perf 進行效能分析

`clz` 分析

`sqrti` 分析

實作：開平方根向上取整
$⌈ \sqrt{N} ⌉$

實作：不依賴除法的浮點數開平方根 `sqrtf`