2025q1 Homework2 (quiz1+2)

contributed by < Mike1117 >

進度記錄

進度記錄

quiz 1

測驗一

• 填空
• 延伸問題：
  • 解釋上方程式碼運作原理
  • 在現有的程式碼基礎上，撰寫合併排序操作

測驗二

• 填空
• 延伸問題：
  • 解釋上方程式碼運作的原理
  • 補完程式碼，使其可獨立執行
  • 提供相關的測試程式碼
  • 參閱 memory-allocators，針對補完 (及後續改進) 的記憶體配置器進行效能評比
  • 解讀其效能表現

測驗三

• 填空
• 延伸問題：
  • 解釋上述程式碼運作原理
  • 研讀〈A comparative study of linked list sorting algorithms〉
  • 分析針對雙向鏈結串列的排序演算法考量
  • 運用 Linux 核心風格的 List API 予以實作

---

quiz 2

測驗一

• 填空
• 延伸問題：
  • 解釋上方程式碼運作原理
  • 改進 random_shuffle_array
  • 探討 list_for_each_entry_safe 構建的迴圈中：若將 list_move_tail 換為 list_move，為何無法滿足 stable sorting？
  • 將程式碼整合進 lab0 提及的 qtest
  • 探討環狀雙向鏈結串列的排序效能
  • 善用 perf 等效能分析工具：
    • 探討包含 Linux 核心 list_sort 在內排序實作的效能表現
    • 充分解釋結果

測驗二

• 填空
• 延伸問題：
  • 解釋上述程式碼
  • 探討擴充為 ⌈𝑥⌉ (向上取整數) 的實作：
    • 如何調整並保持只用整數加減及位元操作
  • 參照計算機結構測驗題 C 及其注釋：
    • 以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf
    • 確保符合 IEEE 754 規格
    • 對照 sqrtf, rsqrt, reciprocal 在 Arm assembly 的實作
  • 參照「從 √2 的存在談開平方根的快速運算」：
    • 以 C 語言實作「藉由查表的平方根運算」
    • 比較不同手法的整數開平方根效能
  • 若發現效能改進的機會：
    • 準備提交改進 int_sqrt 程式碼到 Linux 核心

測驗三

• 填空
• 延伸問題：
  • 解釋上述程式碼運作原理
  • 提供測試程式碼
  • 針對 Linux 核心的 hash table 實作：
    • 提供更多圖例
    • 揣摩 Linux 核心開發者的設計思路
  • 進行《The Art of Computer Programming》(vol 3) section 6.4 exercise 8：
    • 證明 Theorem S
  • 注意：
    • Linux 核心內部大量使用 hash table
    • 並非所有雜湊函數都能減少碰撞及避免 clustering
    • 探討可能的改進空間
  • 探討 Linux 核心中使用 hash table 的應用案例：
    • 至少分析兩個案例
    • 列出原始程式碼並分析
    • 斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素

第 1 周測驗題

測驗一

填空部分

AAAA = &l->head

BBBB = before

CCCC = &(*p)->next

DDDD = (*p)->next

延伸問題

解釋上方程式碼運作原理

size_t list_size(const list_t *list)

返回鏈結串列的 size

static list_t *list_reset(void)

依序設定每個節點的 value 為 i ，清除 next 的指向，清空 head 使鏈結串列為空。

static char *test_list(void)

依序測試將節點插入到鏈接串列的開頭、尾端。

static char *test_suite(void)

執行測試 test_list，若失敗會回傳錯誤訊息

int main(void)

主函式，負責執行測試、輸出測試結果以及執行的測試數量。

static inline void list_insert_before(list_t *l, list_item_t *before, list_item_t *item)

for (p = &l->head; *p != before; p = &(*p)->next)
此 for 迴圈的作用為找到指向 before 的指標
故初始條件應設為 p = &l->head ，即從鏈結串列的頭節點開始。

退出條件則設為 *p != before ，即 p 指向 before 的指標時退出迴圈。

每次迴圈執行時， p 都會被更新為下一個節點的 next 指標。
找到指向 before 的指標後，先將 *p 之值更新為 item，即將指向 before 的指標更新為指向我們欲插入的 item 。

再將 (*p)->next 更新為 before ，將 item 的下一個節點設為 before 。

在現有的程式碼基礎上，撰寫合併排序操作

list_item_t *merge_two_list(list_item_t *L1, list_item_t *L2)
{
    if (!L1)
        return L2;
    if (!L2)
        return L1;
    list_item_t *head = NULL;
    list_item_t **ptr = NULL;
    list_item_t **node = NULL;

    head = (L1->value <= L2->value)
                   ? L1
                   : L2;
    ptr = &head->next;
    node = (head == L1) ? &L1 : &L2;
    *node = (*node)->next;
    // cppcheck-suppress knownConditionTrueFalse
    while (L1 && L2) {
        node = (L1->value <= L2->value)
                    ? &L1
                    : &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
        if (*node)
            *node = (*node)->next;
    }
    *ptr = (L1) ? L1 : L2;

    return head;
}

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

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

    list_item_t *mid = slow->next;
    slow->next = NULL;

    list_item_t *left_sorted = merge_sort(head);
    list_item_t *right_sorted = merge_sort(mid);

    return merge_two_list(left_sorted, right_sorted);
}

想法 & 思考

在撰寫此份作業時，我已使用合併排序完成 lab0 中的 q_sort 實作，所以此處之合併排序修改自 lab0 。
需要注意的是 lab0 中的鏈結串列為具有 Dummy head 之雙向鏈結串列，而此處觀察 list.h 中的串列結構，可以發現是具有 Dummy head 之單向鏈結串列，故需要在 lab0 的程式碼上再稍作修改，使其可以正常排序單向鏈結串列。
合併排序是一個採用 Divide and Conquer 的典型應用，故此實作的第一步便是要先實現 Divide 。我們需要將鏈結串列的長度在每次遞迴中縮短一半，較為有效的方法便是使用快慢指標來獲取位於串列中間之節點的位址，如此即可在不斷遞迴中將整個串列 divide 成單節點的串列。
第二步則是需要將已被「打散」的鏈結串列作合併，而合併的同時則是需要比較各節點值的大小，值較小的先合併。這樣每次遞迴回傳的鏈結串列都是 sorted 的。
實作中則將整個合併排序的流程分為兩個函式，merge_sort 會利用快慢指標將鏈結串列不斷分為長為目前一半的子串列，直至剩下單節點後，再透過呼叫 merge_two_list 來依序合併子串列。
而 merge_two_list 中則使用了教材 中提到的指向指標的指標這一方法，將兩個子串列中的節點依大小串接起來，直至其中一串列變空，最後再將剩餘的節點接至已合併串列的尾端。

測驗二

填空部分

EEEE = (*pred_ptr)->r
FFFF = &(*pred_ptr)->r

可以看到填空部分上方的註解中提到 This is the rightmost node in the left subtree 。
即在下方這個 while 迴圈中，我們需要找的是目前此左子樹的最右節點。

while (EEEE)
    pred_ptr = FFFF;

故 while 的條件應設為 (*pred_ptr)->r ，當前節點有右節點時繼續迴圈。
而 while 內則是不斷將 pred_ptr 更新為 &(*pred_ptr)->r ，即右節點。

延伸問題

解釋上方程式碼運作的原理，並嘗試補完程式碼，使其可獨立執行，應提供相關的測試程式碼

block_t **find_free_tree(block_t **root, block_t *target) {
    while (*root && *root != target) { 
        if (target->size < (*root)->size) {
            root = &(*root)->l;
        } else {
            root = &(*root)->r;
        }
    }
    return root;
}

此函式的 input 為 root 及欲尋找之節點 target ，由註解可知 The free tree is a binary search tree ，故尋找目標節點只需比較與當前節點之大小，當前節點較 target 大則向左，反之則向右，直至找到 target 的 pointer 再返回。

block_t *find_predecessor_free_tree(block_t **root, block_t *node) {
    if (!node->l) return NULL;
    block_t *pred = node->l;
    while (pred->r) {
        pred = pred->r;
    }
    return pred;
}

此函式的 input 為 root 及欲尋找 predecessor 之 node 。
而 Predecessor 的定義為：以中序 traverse 時， node 的前一個節點。
所以在 node 有左子樹時， node 的 predecessor 就是 node 的左子樹中最大的節點。
而我們看到在 remove_free_tree 中，呼叫 find_predecessor_free_tree 前，函式會先判斷 if ((*node_ptr)->l && (*node_ptr)->r) 。故在呼叫 find_predecessor_free_tree 時，該 tree 必定有左子樹，所以我們的函式可以簡單地寫成尋找左子樹的最大值，即左子樹之最右節點。
以下是給出的測試程式：

void insert_free_tree(block_t **root, block_t *node) {
    if (!*root) {
        *root = node;
        node->l = node->r = NULL;
        return;
    }
    if (node->size < (*root)->size)
        insert_free_tree(&(*root)->l, node);
    else
        insert_free_tree(&(*root)->r, node);
}

void inorder_traversal(block_t *root) {
    if (!root) return;
    inorder_traversal(root->l);
    printf("%zu ", root->size);
    inorder_traversal(root->r);
}

int main() {
    block_t nodes[7] = {{40, NULL, NULL}, {20, NULL, NULL}, {60, NULL, NULL},
                         {10, NULL, NULL}, {30, NULL, NULL}, {50, NULL, NULL}, {70, NULL, NULL}};
    
    block_t *root = NULL;
    for (int i = 0; i < 7; i++)
        insert_free_tree(&root, &nodes[i]);

    printf("Initial tree: ");
    inorder_traversal(root);
    printf("\n");

    printf("Removing node 20...\n");
    remove_free_tree(&root, &nodes[1]);

    printf("Tree after removal: ");
    inorder_traversal(root);
    printf("\n");

    return 0;
}

該程式先定義一個函式 insert_free_tree ，用以建立 BST。再定義一個函式 inorder_traversal 用以 print 出目前 BST 的 inorder traversal 。
而在 main 函式中則先建立一個 BST 後 print 出他的 inorder traversal ，以前述函式 remove_free_tree 移除一特定節點後再檢驗移除的節點是否正確。
以下是該測試函式的輸出：

Initial tree: 10 20 30 40 50 60 70 
Removing node 20...
Tree after removal: 10 30 40 50 60 70

可以看到

參閱 memory-allocators，針對你補完 (及後續改進) 的記憶體配置器，進行效能評比，並解讀其效能表現

測驗三

填空部分

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

延伸問題

解釋上述程式碼運作原理

void list_construct(struct list_head *list, int n)

加入 value 為 n 的新節點。

void list_free(const struct list_head *head)

清空整個 list 及其記憶體。

static bool list_is_ordered(const struct list_head *head)

檢驗目前的 list 是否有嚴格遞增，無則返回 false ，有則返回 true 。

void shuffle(int *array, size_t n)

Shuffle array，有實作上的缺陷。

int main(int argc, char **argv)

主函式部分，負責建立一個 array 並依序填入 0 - 99999 後進行 shuffle ，再用此 array 建立一個新的 list ，呼叫 quicksort 對 list 進行 sort ，校驗 quicksort 是否實作正確後釋放 list 及 array 的記憶體。

struct list_head *list_tail(struct list_head *head)

會返回 list 最尾端之節點的指標。

int list_length(struct list_head *left

返回 list 的長度。

static void rebuild_list_link(struct list_head *head)

確保雙向鏈結串列的每個節點的 next 以及 prev 鏈結正確，且頭尾相連保證該串列是個 circuit 。所以prev->next = head 及 GGGG 兩行的作用為確保串列頭尾相連，故應填入 head->prev = prev ，使 head 的 next 指向串列的尾端節點。

void quick_sort(struct list_head *list)

該函式是將 Optimized QuickSort — C Implementation (Non-Recursive) 實作於雙向鏈結串列。
先利用 list_length 取得鏈結串列的長度後，建立了兩倍於長度的 陣列 begin ，用以存放待處理的的子串列，模擬遞回的堆疊。
而在外層的 while 迴圈中，L 及 R 分別表示當前要處理之子序列之頭和尾。
當 L 及 R 未指向同一 node 時，會選定 L 作為 pivot ，並在內層的 while 迴圈中比較當前 node 與 pivot 之 value 的大小，較大則加入 right ，較小則加入 left 。
最後再將 left pivot 及 right 依序放入 begin 。
而當 L=R 時，代表目前待處理的串列僅有單個節點，此時就直接將此節點歸入 result ，同時呼叫 i-- ，在進入下一迴圈時處理堆疊中的下一個串列。
迴圈結束後會將 list 的 next 指向已經排序好的 result ，並呼叫 rebuild_list_link 保證鏈結串列的正確性。至此，便可在不遞迴的情況下完成 quicksort 。

研讀〈A comparative study of linked list sorting algorithms〉，分析針對雙向鏈結串列的排序演算法考量，並運用 Linux 核心風格的 List API 予以實作

分析針對雙向鏈結串列的排序演算法考量

運用 Linux 核心風格的 List API 予以實作

Tree Sort實作

void build_tree(struct list_head *head)
{
    if (!head || !head->next) 
        return;
    struct list_head *bst_root = head->next;  // 設定 BST 的根
    int first_time = 0;

    node_t *curr, *safe;
    /*prev = left, next = right*/
    list_for_each_entry_safe(curr, safe, head->next, list){
        if(first_time == 0){
            bst_root->next = NULL;
            bst_root->prev = NULL;
            first_time = 1;
        }
        struct list_head *root = bst_root;
        for(;;){
            if(curr->value > list_entry(root, node_t, list)->value){
                if(root->next){
                    root = root->next;
                }else{
                    root->next = &curr->list;
                    break;
                }
            }else{
                if(root->prev){
                    root = root->prev;
                }else{
                    root->prev = &curr->list;
                    break;
                }
            }
        }
        if(curr->list.next==head){
            curr->list.next = NULL;
            curr->list.prev = NULL;
            break; 
        }
        curr->list.next = NULL;
        curr->list.prev = NULL;
    }
}

void inorder_traversal_rebuild_list(struct list_head *head)
{
    if (!head || !head->next) 
        return;

    struct list_head *bst_root = head->next;
    struct list_head *prev = head;
    struct list_head *first = NULL;
    struct list_head *last = NULL;

    void inorder_helper(struct list_head *node) {
        if (!node) return;

        inorder_helper(node->prev);

        if (!first) first = node;
        if (last) {
            last->next = node;
            node->prev = last;
        }
        last = node;

        inorder_helper(node->next);
    }

    inorder_helper(bst_root);

    if (first) {
        head->next = first;
        first->prev = head;
    }
    if (last) {
        last->next = head;   
        head->prev = last;     
    }
}


void tree_sort(struct list_head *head)
{
    build_tree(head);
    inorder_traversal_rebuild_list(head);
}

第 2 周測驗題

測驗一

填空部分

AAAA = list_first_entry
BBBB = list_del
CCCC = list_move_tail
DDDD = list_add
EEEE = list_splice
FFFF = list_splice_tail

延伸問題

解釋上方程式碼運作原理，改進 random_shuffle_array 也探討 list_for_each_entry_safe 建構的迴圈中，若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

解釋上方程式碼運作原理

static inline int cmpint(const void *p1, const void *p2)

qsort 所需要的比較函式，比較 p1 及 p2 的大小，若 p1 較大則回傳正數，較小則回傳負數，相等則回傳 0 。

#define ARRAY_SIZE(x) (sizeof(x) / sizeof(x[0]))

計算 Array 的大小。

static uint16_t values[256];

宣告一個大小為 256 的陣列存放隨機生成的數。

static inline uint8_t getnum(void)

生成一個 0 ~ 255 之間的隨機數。

static uint16_t get_unsigned16(void)

呼叫 getnum 生成兩個 8-bit 的隨機數，組合成一個 16-bit 的隨機數。

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)

打亂陣列，原實作有缺陷，需在後續修改為 Fisher-Yates Shuffle

int main(void)

主函式，先向陣列中依序填入 0 ~ 255 間的證書，再透過 random_shuffle_array 打亂，並以此 Array 建立一鏈結串列。
隨後以 qsort 及自定義的 list_quicksort 分別對陣列及鏈結串列進行 quick sort 。
再以兩者 sort 完的結果一一進行比較，檢查結果是否相同，若過程中有 error 或最後的結果不同，則會輸出錯誤資訊。

改進 random_shuffle_array

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = 0; i < len; i++) {
        /* WARNING biased shuffling */
        uint16_t j = get_unsigned16() % (i + 1);
        operations[i] = operations[j];
        operations[j] = i;
    }
}

static inline void random_shuffle_array(uint16_t *operations, uint16_t len)
{
    for (uint16_t i = len - 1; i > 0; i--) {
        /* Replace original shuffle with Fisher-Yates Shuffle */
        uint16_t j = get_unsigned16() % (i + 1);
        uint16_t temp = operations[i];
        operations[i] = operations[j];
        operations[j] = temp;
    }
}

原函式的實作會造成 Biased Shuffling ，故此處需修改為正確的 Fisher-Yates Shuffle 實作。

若將 list_move_tail 換為 list_move，為何會無法滿足 stable sorting

在上述程式中，呼叫 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);
}

而這是 list_move_tail 及 list_move 的函式內容：

static inline void list_move(struct list_head *node, struct list_head *head)
{
    list_del(node);
    list_add(node, head);
}

static inline void list_move_tail(struct list_head *node,
                                  struct list_head *head)
{
    list_del(node);
    list_add_tail(node, head);
}

可以看到兩函式的差異僅在於 list_move_tail 呼叫的函式為list_add_tail ，而 list_move 呼叫的函式為 list_add 。
再繼續看到 list_add_tail 及 list_add這兩個函式：

static inline void list_add(struct list_head *node, struct list_head *head)
{
    struct list_head *next = head->next;

    next->prev = node;
    node->next = next;
    node->prev = head;
    head->next = node;
}

static inline void list_add_tail(struct list_head *node, struct list_head *head)
{
    struct list_head *prev = head->prev;

    prev->next = node;
    node->next = head;
    node->prev = prev;
    head->prev = node;
}

可以看到 list_add_tail 是將新的node接入串列的尾端，而 list_add 則是將新的node接入head之後。
假設我們有兩個具有相同值之 node ， A1 及 A2 ，在 compare 之後若使用 list_move_tail ，在新的串列中他們的相對位置仍然會是 A1 在前， A2 在後；若使用 list_move ，兩節點之相對位置則會變成 A2 在前， A1 在後，不符合 stable sort 之定義。

將程式碼整合進 lab0 提及的 qtest，並探討環狀雙向鏈結串列的排序效能，並善用 perf 一類的效能分析工具，探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

將程式碼整合進 lab0 提及的 qtest

/*Add quick sort*/
static void q_qksort(struct list_head *head)
{
    struct list_head list_less, list_greater;
    element_t *pivot;
    element_t *item = NULL, *is = NULL;

    if (list_empty(head) || list_is_singular(head))
        return;

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

    pivot = list_first_entry(head, element_t, list);
    list_del(&pivot->list);

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

    q_qksort(&list_less);
    q_qksort(&list_greater);

    list_add(&pivot->list, head);
    list_splice(&list_less, head);
    list_splice_tail(&list_greater, head);
}

bool do_qksort(int argc, char *argv[])
{
    if (argc != 1) {
        report(1, "%s takes no arguments", argv[0]);
        return false;
    }

    int cnt = 0;
    if (!current || !current->q)
        report(3, "Warning: Calling sort on null queue");
    else
        cnt = q_size(current->q);
    error_check();

    if (cnt < 2)
        report(3, "Warning: Calling sort on single node");
    error_check();

    set_noallocate_mode(true);

/* If the number of elements is too large, it may take a long time to check the
 * stability of the sort. So, MAX_NODES is used to limit the number of elements
 * to check the stability of the sort. */
#define MAX_NODES 100000
    struct list_head *nodes[MAX_NODES];
    unsigned no = 0;
    if (current && current->size && current->size <= MAX_NODES) {
        element_t *entry;
        list_for_each_entry(entry, current->q, list)
            nodes[no++] = &entry->list;
    } else if (current && current->size > MAX_NODES)
        report(1,
               "Warning: Skip checking the stability of the sort because the "
               "number of elements %d is too large, exceeds the limit %d.",
               current->size, MAX_NODES);

    if (current && exception_setup(true))
        q_qksort(current->q);
    exception_cancel();
    set_noallocate_mode(false);

    bool ok = true;
    if (current && current->size) {
        for (struct list_head *cur_l = current->q->next;
             cur_l != current->q && --cnt; cur_l = cur_l->next) {
            /* Ensure each element in ascending/descending order */
            element_t *item, *next_item;
            item = list_entry(cur_l, element_t, list);
            next_item = list_entry(cur_l->next, element_t, list);
            if (!descend && strcmp(item->value, next_item->value) > 0) {
                report(1, "ERROR: Not sorted in ascending order");
                ok = false;
                break;
            }

            if (descend && strcmp(item->value, next_item->value) < 0) {
                report(1, "ERROR: Not sorted in descending order");
                ok = false;
                break;
            }
            /* Ensure the stability of the sort */
            if (current->size <= MAX_NODES &&
                !strcmp(item->value, next_item->value)) {
                bool unstable = false;
                for (unsigned i = 0; i < MAX_NODES; i++) {
                    if (nodes[i] == cur_l->next) {
                        unstable = true;
                        break;
                    }
                    if (nodes[i] == cur_l) {
                        break;
                    }
                }
                if (unstable) {
                    report(
                        1,
                        "ERROR: Not stable sort. The duplicate strings \"%s\" "
                        "are not in the same order.",
                        item->value);
                    ok = false;
                    break;
                }
            }
        }
    }
#undef MAX_NODES

    q_show(3);
    return ok && !error_check();
}

......
    
ADD_COMMAND(qksort, "Sort queue in ascending order with quick sort", "");

探討環狀雙向鏈結串列的排序效能

探討包含 Linux 核心 list_sort 在內排序實作的效能表現並充分解釋

以 Python 撰寫自動化測試程式並生成圖表，可以看到兩者在執行時間上幾乎沒有差異。

測驗二

填空部分

GGGG = 14
HHHH = 2
IIII = 0
JJJJ = 3
KKKK = 2
LLLL = 1
MMMM = ~1
NNNN = 1
PPPP = 2

延伸問題

解釋上述程式碼，並探討擴充為

$\lceil \sqrt{x}\rceil$ (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

解釋上述程式碼

clz2(uint32_t x, int c)

static const int mask[] = {0, 8, 12, 14};
static const int magic[] = {2, 1, 0, 0};

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 == 3)
        return upper ? magic[upper] : KKKK + magic[lower];
    return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + LLLL);
}

該程式先定義了兩個全域整數陣列 mask 及magic。 mask 用以遮蔽高位元、提取低位元。
而 magic 則是在最後剩下二位元時直接獲得 leading zero 的數量。
而函式主體部分則是根據傳入值 c 判定當前的遞迴層數，用以切割高位元及低位元。若高位元非 0，則只需計算高位元的 leading zero 。若高位元皆為 0 ，則再計算低位元的 leading zero 並加上高位元的 bit 數。
當傳入值 c = 3 時，代表當前的高低位元會分別剩下 2 bit ，此時只需使用 magic 陣列即可直接獲得 leading zero 的數量。

uint64_t sqrti(uint64_t x)

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;
}

並探討擴充為 (向上取整數) 實作，該如何調整並保持只用整數加減及位元操作

參照計算機結構測驗題 C 及其注釋，以 C 語言 (搭配 GNU extension) 撰寫不依賴除法指令的 sqrtf，確保符合 IEEE 754 規格。對照 sqrtf, rsqrt, reciprocal implementations in Arm assembly

以 C 語言撰寫不依賴除法指令的 sqrtf

參照從 √2 的存在談開平方根的快速運算提到的「藉由查表的平方根運算」，以 C 語言實作，並比較不同手法的整數開平方根效能

以 C 語言實作藉由查表的平方根運算

測驗三

填空部分

AAAA = map->bits
BBBB = map->
CCCC = first->pprev
DDDD = n->pprev
EEEE = n->pprev

延伸問題

解釋上述程式碼運作原理，應提供測試程式碼

解釋上述程式碼運作原理

map_t *map_init(int bits)

初始化 hash map ，傳入值 bits 為 map 的大小。

void map_add(map_t *map, int key, void *data)

為 map 加入新的鍵值，會先檢查要加入的 key 是否已在 map 中，若無再作加入。

void map_deinit(map_t *map)

釋放 hash table 及其內部所有節點的記憶體。

int *twoSum(int *nums, int numsSize, int target, int *returnSize)

建立一個大小為 10 的 hash table ， traverse 陣列中每一個元素，檢查目標值與其相減後的值是否存在 hash table 中，若存在，則可直接返回自己與 table 中對應值的 index 。
若不存在，則將自身的值加入 hash table 中，以利其他元素查找。

測試程式碼

首先需要加入標頭檔及定義缺失的巨集 MAP_HASH_SIZE

#include <stdio.h>
#include <stdlib.h>
#include "list.h"

#define MAP_HASH_SIZE(bits) (1 << bits)

查閱 Two Sum 的 Description ，要求為 return indices of the two numbers such that they add up to target。
故測試主函式如下：

void printArray(int *arr, int size) {
    if (size == 0) {
        printf("No solution found.\n");
        return;
    }
    printf("Indices: [%d, %d]\n", arr[0], arr[1]);
}

int main() {
    int returnSize;
    
    // Test Case 1
    int nums1[] = {2, 7, 11, 15};
    int target1 = 9;
    int *result1 = twoSum(nums1, 4, target1, &returnSize);
    printf("Test Case 1: ");
    printArray(result1, returnSize);
    free(result1);
    
    // Test Case 2
    int nums2[] = {3, 2, 4};
    int target2 = 6;
    int *result2 = twoSum(nums2, 3, target2, &returnSize);
    printf("Test Case 2: ");
    printArray(result2, returnSize);
    free(result2);
    
    // Test Case 3
    int nums3[] = {3, 3};
    int target3 = 6;
    int *result3 = twoSum(nums3, 2, target3, &returnSize);
    printf("Test Case 3: ");
    printArray(result3, returnSize);
    free(result3);
    
    // Test Case 4: No solution
    int nums4[] = {1, 2, 3, 4};
    int target4 = 10;
    int *result4 = twoSum(nums4, 4, target4, &returnSize);
    printf("Test Case 4: ");
    printArray(result4, returnSize);
    free(result4);
    
    return 0;
}

首先定義一函式 printArray 用以 print 結果。
其次提供 4 測試例，預期輸出為[0, 1]，[1, 2]，[0, 1]，[].
最終輸出如下：

Test Case 1: Indices: [1, 0]
Test Case 2: Indices: [2, 1]
Test Case 3: Indices: [1, 0]
Test Case 4: No solution found.

與預期結果相符。

進行《The Art of Computer Programming》(vol 3) 一書section 6.4 的 exercise 8，也就是證明 Theorem S

證明 Theorem S

探討 Linux 核心中使用 hash table 的應用案例，至少二項，應當列出原始程式碼並分析，斟酌搭配 git log 以得知 Linux 核心開發者變更程式碼的考量因素

Linux 核心中使用 hash table 的應用案例

linux/kernel/user.c

include/linux/fprobe.h