2025q1 Homework2 (quiz1+2)

# 2025q1 Homework2 (quiz1+2) contributed by < `weiso131` > {%hackmd NrmQUGbRQWemgwPfhzXj6g %} # 第一週測驗 `1` ## 填空 - `AAAA` : `&l` - `BBBB` : `before` - `CCCC` : `&(*p)->next` - `DDDD` : `item->next` ## 程式運作原理 ### list_insert_before 運作原理 ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled, fillcolor=lightgray]; head_ptr [label="{l | <head >head}"]; indirect [label="p", shape=note, fillcolor=lightyellow]; node1 [label="{ data | <next >next }"]; node2 [label="{ before | next }"]; node3 [label="{ data | next }"]; null [label="NULL", shape=plaintext]; node4 [label="{ item | next }"]; // head -> node1 head_ptr -> node1 [label="head"]; // node1 -> node2 -> node3 -> NULL node1 -> node2 [label="next"]; node2 -> node3 [label="next"]; node3 -> null [label="next"]; // indirect 指向 head_ptr（間接指標） indirect -> head_ptr: next [style=dashed, color=blue]; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled, fillcolor=lightgray]; head_ptr [label="{l | <head >head}"]; indirect [label="p", shape=note, fillcolor=lightyellow]; node1 [label="{ data | <next >next }"]; node2 [label="{ before | next }"]; node3 [label="{ data | next }"]; null [label="NULL", shape=plaintext]; node4 [label="{ item | next }"]; // head -> node1 head_ptr -> node1 [label="head"]; // node1 -> node2 -> node3 -> NULL node1 -> node2 [label="next"]; node2 -> node3 [label="next"]; node3 -> null [label="next"]; // indirect 指向 head_ptr（間接指標） indirect -> node1: next [style=dashed, color=blue]; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled, fillcolor=lightgray]; head_ptr [label="{l | <head >head}"]; indirect [label="p", shape=note, fillcolor=lightyellow]; node1 [label="{ data | <next >next }"]; node2 [label="{ before | next }"]; node3 [label="{ data | next }"]; null [label="NULL", shape=plaintext]; node4 [label="{ item | next }"]; // head -> node1 head_ptr -> node1 [label="head"]; // node1 -> node2 -> node3 -> NULL node1 -> node4 [label="next"]; node2 -> node3 [label="next"]; node3 -> null [label="next"]; // indirect 指向 head_ptr（間接指標） indirect -> node1: next [style=dashed, color=blue]; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled, fillcolor=lightgray]; head_ptr [label="{l | <head >head}"]; indirect [label="p", shape=note, fillcolor=lightyellow]; node1 [label="{ data | <next >next }"]; node2 [label="{ before | next }"]; node3 [label="{ data | next }"]; null [label="NULL", shape=plaintext]; node4 [label="{ item | next }"]; // head -> node1 head_ptr -> node1 [label="head"]; // node1 -> node2 -> node3 -> NULL node1 -> node4 [label="next"]; node2 -> node3 [label="next"]; node3 -> null [label="next"]; node4 -> node2 [label="next"]; // indirect 指向 head_ptr（間接指標） indirect -> node1: next [style=dashed, color=blue]; } ``` ### merge_sort 實作 ```c list_item_t *merge(list_item_t *l, list_item_t *r, int descend) { list_item_t *head = NULL, **indir = &head; while (1) { if (l->value > r->value == descend) { *indir = l; indir = &l->next; l = l->next; if (!l) { *indir = r; break; } } else { *indir = r; indir = &r->next; r = r->next; if (!r) { *indir = l; break; } } } return head; } list_item_t *merge_sort(list_item_t *head, int descend) { if (head->next == NULL) return head; list_item_t *l = head, *last_r = head, *r = head->next, *fast = head->next; while (fast != NULL && fast->next != NULL) { last_r = r; r = r->next; fast = fast->next->next; } last_r->next = NULL; l = merge_sort(l, descend), r = merge_sort(r, descend); return merge(l, r, descend); } ``` # 第一週測驗 `2` ## 填空 - `EEEE`: `(*pred_ptr)->r` - `FFFF`: `&(*pred_ptr)->r` ## `remove_free_tree` 解讀 ### `l == r == NULL` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n2: l [style=dashed, color=blue]; //pred_ptr -> n2: n2node [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> null9; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n2: l [style=dashed, color=blue]; //pred_ptr -> n2: n2node [style=dashed, color=blue]; } ``` ### `l != NULL || r != NULL` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> null9; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4: l [style=dashed, color=blue]; //pred_ptr -> n2: n2node [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n3:n3node; n4:r -> n6:n6node; n2:l -> null9; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4: l [style=dashed, color=blue]; //pred_ptr -> n2: n2node [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; //pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n3:n3node; n4:r -> n6:n6node; n2:l -> null9; n2:r -> null1; n6:l -> n5:n5node; n6:r -> n7:n7node; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4: l [style=dashed, color=blue]; //pred_ptr -> n2: n2node [style=dashed, color=blue]; } ``` ### `l != NULL && r != NULL` #### `*pred_ptr != (*node_ptr)->l` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 root [label="{root}"]; n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; root -> n4; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> root; pred_ptr -> n2 : r [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 root [label="{root}"]; n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; root -> n4; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> null9; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> root; pred_ptr -> n2 : r [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 root [label="{root}"]; n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; root -> n3; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> null3; n4:r -> null4; n2:l -> n1:n1node; n2:r -> null9; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> n2; n3:r -> n6; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> root; pred_ptr -> n2 : r [style=dashed, color=blue]; } ``` #### `*pred_ptr == (*node_ptr)->l` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4 : l; pred_ptr -> n2 : l [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4:l; pred_ptr -> n2 : l [style=dashed, color=blue]; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; pred_ptr [label="pred_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> 2 | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; null9 [label="NULL", shape=plaintext]; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n1:n1node; n4:r -> n6:n6node; n2:l -> null9; n2:r -> null2; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> n3; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4:l; pred_ptr -> n2 : l [style=dashed, color=blue]; } ``` ## 補完程式碼 ### find_free_tree ```c block_t **find_free_tree(block_t **root, block_t *target) { block_t **node_ptr = root; while (*node_ptr != target && *node_ptr != NULL) { if (target->size > (*node_ptr)->size) node_ptr = &(*node_ptr)->r; else node_ptr = &(*node_ptr)->l; } return node_ptr; } ``` #### 解說 ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="node_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> target | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; root -> n4; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> root; } ``` ```graphviz digraph BST { rankdir=TB; node [shape=record, style=filled, fillcolor=lightgray]; indirect [label="return: node_ptr", shape=note, fillcolor=lightyellow]; // 節點 n4 [label="{ <n4node> 4 | {<l> l | <r> r }}"]; n2 [label="{ <n2node> target | {<l> l | <r> r }}"]; n6 [label="{ <n6node> 6 | {<l> l | <r> r }}"]; n1 [label="{ <n1node> 1 | {<l> l | <r> r }}"]; n3 [label="{ <n3node> 3 | {<l> l | <r> r }}"]; n5 [label="{ <n5node> 5 | {<l> l | <r> r }}"]; n7 [label="{ <n7node> 7 | {<l> l | <r> r }}"]; // NULL 節點 null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; null4 [label="NULL", shape=plaintext]; null5 [label="NULL", shape=plaintext]; null6 [label="NULL", shape=plaintext]; null7 [label="NULL", shape=plaintext]; null8 [label="NULL", shape=plaintext]; root -> n4; // 建立連線（從 l、r port 出發，接到子節點的 <xxxnode> port） n4:l -> n2:n2node; n4:r -> n6:n6node; n2:l -> n1:n1node; n2:r -> n3:n3node; n6:l -> n5:n5node; n6:r -> n7:n7node; n1:l -> null1; n1:r -> null2; n3:l -> null3; n3:r -> null4; n5:l -> null5; n5:r -> null6; n7:l -> null7; n7:r -> null8; indirect -> n4:l; } ``` ### insert_free_tree ```c void insert_free_tree(block_t **root, block_t *target) { block_t **node_ptr = find_free_tree(root, target); *node_ptr = target; } ``` ### init_block ```c block_t *init_block(size_t size) { block_t *block = malloc(sizeof(block_t)); block->size = size; block->l = block->r = NULL; return block; } ``` ### 測試程式 ```c void block_test() { for (int i = 0;i < N;i++) { size_t size = rand() % 8192; blocks[i] = init_block(size); insert_free_tree(&root, blocks[i]); } for (int i = 0;i < N;i++) { remove_free_tree(&root, blocks[i]); block_t **find = find_free_tree(&root, blocks[i]); assert(*find == NULL); free(blocks[i]); blocks[i] = NULL; } printf("All test complete!!!\n"); } ``` #### 解說 ## 自訂記憶體配置器 [github](https://github.com/weiso131/Customize_allocator) 參考 [memory-allocators](https://github.com/mtrebi/memory-allocators) 的 free list allocator。這種記憶體分配器屬於通用型分配器，利用一個資料結構(通常是鏈結串列或紅黑樹)紀錄可供使用的記憶體區塊，在使用者請求分配時，在這個資料結構尋找合適的區塊提供給使用者。另外，若在釋放記憶體時，發現有相鄰的記憶體區塊是可用的，這種實作方法會將其合併。要以時間複雜度 $O(1)$ 確認是否能合併，可以使用雙向鏈結串列維護其順序，以方便查詢。文中提到可以用鍊結串列或是紅黑樹維護，我嘗試使用二元搜尋樹代替紅黑樹，實作這種記憶體分配器。在不發生樹嚴重傾斜的情況下，查詢的時間複雜度與紅黑樹相同，皆是 $O(log(n))$。而在測驗題中也有提供相關實作，可直接使用。至於雙向鏈結串列，在實作過程中發現，若是環狀的鏈結串列，在插入節點時就沒有判斷下一項是否為空指標的問題，因此我使用 list.h 的資料結構與 API 來維護這個雙向鏈結串列。 ### 功能簡述這些是這個分配器提供給使用者的主要功能定義在 [includes/free_list_alloc.h](https://github.com/weiso131/Customize_allocator/blob/main/includes/free_list_alloc.h) - `void init_fl(size_t size);` 根據使用者提供的size，設定這個記憶體分配器的總分配空間大小上限 - `void *fl_alloc(size_t size)` 分配使用者需要的記憶體空間，分配成功則回傳該記憶體的位址分配失敗或是 size 為 0 則回傳 NULL - `void fl_free(void *ptr)` 將使用者傳入的指標對應的空間釋放若傳入空指標則不做任何事情若傳入已經釋放過，或是不屬於 init_fl 初始化的記憶體，則屬於 undefine behavior 與 C 語言原生的 free 類似(參考: C standard (ISO/IEC 9899:2011 §7.20.3.2)) ### `init_fl` #### 步驟 1. 利用 init_block 建立一個初始 block (root_block)。 2. 把這個 block 設定為 tree_root（BST 根節點）。 3. 建立一個 root_head，為雙向鏈結串列的頭節點。 4. 將 root_block 加入雙向鏈結串列（使用 list_add）。 #### 說明 1. 這個新的 block 是一個全新可用的區塊，所以直接加入二元搜尋樹 2. 先使用 root_block 儲存這個分配器全部的可用區塊，再將 tree_root 設定成 root_block ，可以在最後方便使用者一次釋放所有空間，不會因為二元搜尋樹根節點的改變而無法一次釋放 ### `fl_alloc` #### 步驟 1. 使用 find_block_by_size() 找一個合適的 block 2. 從 BST 移除該 block ，代表這個 block 不再是未使用空間 3. 分割多餘空間： - 若剩餘空間足夠放一個 block 結構和額外資料 ➜ 建立新 block (unuse)。 - 重新設定兩個區塊所持有的空間 - 將 unuse 插入鏈結串列(在原本的 block 後方)，並加入二元搜尋樹。 4. 標記分配的 block 為已使用 #### 說明 1. 若剩餘空間小於等於 block 結構的大小，則無法正常成為一個可使用的 block，此時儘管超出使用者要求的記憶體一些，仍會一次將這些記憶體都提供給使用者 #### `find_block_by_size` - 找到最小大於等於使用者要求大小的區塊 - 在迴圈中，若最後找不到相同大小的區塊時， find 會變成 NULL - 為了確保找到的區塊絕對大於使用者要求大小，利用 last_bigger 儲存最後一個往左，也就是最後一個發現比目標大的區塊的指標 >[dded92d](https://github.com/weiso131/Customize_allocator/commit/dded92dd1f87b868ff0ab5a5bffe884028fa630b) - find 為 NULL 的時候會將其設為 last_bigger ，若 size 大於所有可用區塊，就會因為尋找過程中一直向右， last_bigger 仍為 NULL ，符合需求 ### `fl_free` #### 步驟 1. 檢查時否未使用 2. 標記 block 為未使用 3. 插入二元搜尋樹 4. 呼叫 try_merge() 嘗試合併周圍未使用區塊 #### `try_merge` 1. 檢查 block 的 list.next 和 list.prev 是否是未使用。 2. 若是 ➜ 呼叫 merge_b_to_a() #### `merge_b_to_a` 1. 將 b 從 BST 和 linked list 移除。 2. 將 a 從 BST 移除。 3. 計算合併後新大小 ➜ a->size = a->size + b->size + sizeof(block_t)。 4. 將合併後的 a 插回 BST ##### 說明 - 因為合併大小時，可能會改變二元搜尋樹的性質，所以要先將 a 從樹上移除 >[5c0da11](https://github.com/weiso131/Customize_allocator/commit/5c0da119bb05f29e360428c54bc30cfb6b5f7b8e) ### 效能測試 [測試程式](https://github.com/weiso131/Customize_allocator/blob/main/time_test.c) ![image](https://hackmd.io/_uploads/BylSLXlh1x.png =70%x) - 圖為隨機執行 alloc / free 1000000 次所花費的時間累積圖 - 如圖，目前的分配器效能明顯比 malloc 差使用 perf 尋找效能瓶頸 ![image](https://hackmd.io/_uploads/HkedLbmhkl.png) - 可以發現 find_free_tree 佔用了非常大量的時間 - 查看組合語言可以看到 cmp 前最後一個 dereference 非常花時間，這可能對應到原始碼的 `(*node_ptr)->size` ``` 0.07 │25: mov -0x20(%rbp),%rax ▒ 0.71 │ mov (%rax),%rax ▒ 0.13 │ mov -0x8(%rbp),%rdx ▒ 53.47 │ mov (%rdx),%rdx ``` - 似乎與太多的 cache miss 發生有關 ![image](https://hackmd.io/_uploads/rJJ3_WXhkg.png) ### 嘗試減少 `find_free_tree` 使用 - 參考 [`rota1001` 開發紀錄](https://hackmd.io/@rota1001/linux2025-homework2#%E6%B8%AC%E9%A9%97-2) ![image](https://hackmd.io/_uploads/S1pr2X73yg.png) 效能或許有些微提昇，使用 t 檢定驗證 ```python= def calculate_cohens_d(x1, x2): # Pooled standard deviation nx = len(x1) ny = len(x2) pooled_std = np.sqrt(((nx - 1)*np.var(x1, ddof=1) + (ny - 1)*np.var(x2, ddof=1)) / (nx + ny - 2)) d = (np.mean(x1) - np.mean(x2)) / pooled_std return d def compare_groups(free_list, new_free_list): # Welch's t-test（自動考慮變異數不等） t_value, p_value = ttest_ind(free_list, new_free_list, equal_var=False) # 自由度由 ttest_ind 自動處理（Welch 方法） cohen_d = calculate_cohens_d(free_list, new_free_list) print(f"✅ Welch's t-test 結果：") print(f"t 值：{t_value:.4f}") print(f"p 值：{p_value:.4f} {'（顯著）' if p_value < 0.05 else '（不顯著）'}") print(f"Cohen's d 效果量：{cohen_d:.4f}") print(f"效能提升倍率：{free_list.sum() / new_free_list.sum():.4f}") compare_groups(free_list, new_free_list) ``` 輸出： ``` ✅ Welch's t-test 結果： t 值：54.8427 p 值：0.0000 （顯著） Cohen's d 效果量：0.0776 效能提升倍率：1.0997 ``` >[8e833ec](https://github.com/weiso131/Customize_allocator/commit/8e833ec4e9bdd3247775fe1f5c0945c2887144a5) # 第一週測驗 `3` ## 填空 - `GGGG`: `head->prev=prev` - `HHHH`: `list_entry(pivot,node_t,list)->value` - `IIII`: `list_entry(n,node_t,list)->value` - `JJJJ`: `pivot` - `KKKK`: `right` ## `rebuild_list_link` 解說 node 不斷往 next prev 緊跟在 node 後面當 node 為 NULL 時，代表鍊結串列的最後一個節點找到了此時 prev 就是最後一個節點 ## `quick_sort` 解說 ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; list [label="list | {<prev>perv | <next>next } "]; begin [label="begin: | {4}"]; node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> node2: head; node2:next -> node3:head; node3:next -> node4:head; node4:next -> node5:head; node5:next -> list: prev; list:next -> node1:head; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; pivot [label="pivot", style=filled, fillcolor=lightyellow] p [label="p", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null1 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> node2: head; node2:next -> node3:head; node3:next -> node4:head; node4:next -> node5:head; node5:next -> null1:head; pivot -> node1: head; p -> node2: head; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; pivot [label="pivot", style=filled, fillcolor=lightyellow] p [label="p", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null1 [label="NULL"] null2 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> null2; node2:next -> node3:head; node3:next -> node4:head; node4:next -> node5:head; node5:next -> null1:head; pivot -> node1: head; p -> node3: head; right -> node2; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; pivot [label="pivot", style=filled, fillcolor=lightyellow] p [label="p", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null1 [label="NULL"] null2 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> null2; node2:next -> node3:head; node3:next -> node4:head; node4:next -> node5:head; node5:next -> null1:head; pivot -> node1: head; p -> null1; right -> node2; left -> node5; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; pivot [label="pivot", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null1 [label="NULL"] null2 [label="NULL"] null3 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> null2; node2:next -> node3:head; node3:next -> node4:head; node4:next -> null3; node5:next -> null1; pivot -> node1: head; right -> node2; left -> node5; begin [label="begin: | 3 | 4| 8"]; } ``` 稍微跳過幾個步驟 ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; result [label="result", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null1 [label="NULL"] null2 [label="NULL"] null3 [label="NULL"] null4 [label="NULL"] null5 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> null2; node2:next -> null4; node3:next -> null5; node4:next -> null3; node5:next -> null1; right -> node3: head; left -> node3: head; begin [label="begin: | 3 | 4| 6 | 7"]; result -> node2: head; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; result [label="result", style=filled, fillcolor=lightyellow] right [label="right", style=filled, fillcolor=lightyellow] left [label="left", style=filled, fillcolor=lightyellow] null4 [label="NULL"] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> node4: head; node2:next -> null4; node3:next -> node2: head; node4:next -> node3: head; node5:next -> node1: head; right -> node5: head; left -> node5: head; begin [label="begin: | 3"]; result -> node5: head; } ``` ```graphviz digraph LinkedList { rankdir=LR; node [shape=record, style=filled]; list [label="list | {<prev>perv | <next>next } "]; result [label="result", style=filled, fillcolor=lightyellow] node1 [label="{{4 | {<head> list_head | <next >next}}}"]; node2 [label="{{8 | {<head> list_head | <next >next}}}"]; node3 [label="{{7 | {<head> list_head | <next >next}}}"]; node4 [label="{{6 | {<head> list_head | <next >next}}}"]; node5 [label="{{3 | {<head> list_head | <next >next}}}"]; node1: next -> node4: head; node3:next -> node2: head; node4:next -> node3: head; node5:next -> node1: head; result -> node5: head; list: next -> node5: head; list: prev -> node2: head; node2: next -> list: head; } ``` # 第二週測驗 1 ## 填空 - `AAAA`: `list_first_entry` - `BBBB`: `list_del` - `CCCC`: `list_move_tail` - `DDDD`: `list_add` - `EEEE`: `list_splice` - `FFFF`: `list_splice_tail` ## `list_quicksort` 解釋 1. 將 list 的第一項作為 pivot ，並移出環狀鍊結串列 2. 比 pivot 小的節點加入 list_less ，比 pivot 大的節點加入 list_greater ，加入時使用 list_move_tail 維持環狀鍊結串列的特性，同時滿足 stable sorting 3. list_less 與 list_greater 各自進行 list_quicksort 4. 將 pivot, list_less, list_greater 合併 ## 修正 `random_shuffle_array` ### 測試程式使用 4 個元素的陣列執行 shuffle 1e6 次紀錄每種排列的出現次數再計算卡方值 ```c static int index_form[4][4][4]; #define SHUFFLE_TIMES 1000000 #define FACTORIAL_4 24 void build_lookup_table() { int index = 0; uint16_t perm[4] = {1, 2, 3, 4}; // Generate all 4! permutations using stdlib's next_permutation for (int a = 1; a <= 4; ++a) for (int b = 1; b <= 4; ++b) if (b != a) for (int c = 1; c <= 4; ++c) if (c != a && c != b) for (int d = 1; d <= 4; ++d) if (d != a && d != b && d != c) index_form[a - 1][b - 1][c - 1] = index++; } int main() { uint16_t array[4] = {0, 1, 2, 3}; uint32_t count[FACTORIAL_4] = {0}; build_lookup_table(); for (int i = 0; i < SHUFFLE_TIMES; ++i) { random_shuffle_array(array, 4); int idx = index_form[(int)array[0]][(int)array[1]][(int)array[2]]; count[idx]++; } double expected = (double)SHUFFLE_TIMES / FACTORIAL_4; double chi_squared = 0.0; for (int i = 0; i < FACTORIAL_4; ++i) { double diff = count[i] - expected; chi_squared += (diff * diff) / expected; } printf("Chi-squared value: %.4f\n", chi_squared); return 0; } ``` ### 原本的 `random_shuffle_array` 輸出： ``` Chi-squared value: 122688.7850 ``` 卡方值遠高於 $\chi^2_{23,0.05}=35.1725$ ### 使用 `fisher_yates_shuffle` 參考 lab0 提供的 shuffle 演算法 ```c static inline void fisher_yates_shuffle(uint16_t *operations, uint16_t len) { for (uint16_t i = 0;i < len;i++) { uint16_t new = len - i - 1; uint16_t old = get_unsigned16() % (new + 1); uint16_t save = operations[new]; operations[new] = operations[old]; operations[old] = save; } } ``` 輸出： ``` Chi-squared value: 21748.5402 ``` 雖然有減少，但其卡方值仍遠高於 $\chi^2_{23,0.05}=35.1725$ ### 使用 `rand` 代替 `get_unsigned16` ```diff uint16_t new = len - i - 1; - uint16_t old = get_unsigned16() % (new + 1); + uint16_t old = rand() % (new + 1); uint16_t save = operations[new]; ``` 輸出： ``` Chi-squared value: 10.5795 ``` 卡方值小於 $\chi^2_{23,0.05}=35.1725$ 無證據說明這個 shuffle 是不公平的 ## `list_move_tail` 換為 `list_move` 無法滿足 stable sorting # 第二週測驗 2 ## 填空 - `GGGG`: `14` - `HHHH`: `2` - `IIII`: `0` - `JJJJ`: `3` - `KKKK`: `2` - `LLLL`: `1` - `MMMM`: `~1` - `NNNN`: `1` - `PPPP`: `2` ## `clz32` ### 解說 1. 先將一個數字藉由 bit mask 切分成 `upper` 與 `lower` 2. 檢查 `upper` 是否為 0 ，若不是 0 ，代表 leading zero 在 `upper` 裡面，對 `upper` 執行 clz32。反之， leading zero 在 lower ，此時加上 `(16 >> c)` 正是前方的位元數量。 3. 重複執行直到 `c == 3` ，此時 `upper` 與 `lower` 都只剩兩個 bits 的長度，若 `upper` 不為 0 ，將 `upper` 帶入 `magic` 可做最後的計算。反之， `+2` 然後對 `lower` 最類似的事情。 #### mask 補充最後只剩 2 bits ，代表會有四種可能 - 00: 前方累計位元數 +2 即是 leading zero 的位置 - 01: 前方累計位元數 +1 即是 leading zero 的位置 - 10: 前方累計位元數即是 leading zero 的位置 - 11: 前方累計位元數即是 leading zero 的位置 ## `sqrti` ### 解說題目中的 `sqrti` 其實就是 [Digit-by-digit Method](https://hackmd.io/@sysprog/sqrt#Digit-by-digit-Method) 的實作，但直接從原本的函式實作解釋它有些困難，我將會提供從最直觀的實作，一步一步優化到現在狀態的過程。 #### 最直觀實作 ```c int shift = (total_bits - 1 - clz64(x)) & ~1; while (shift >= 0) { m = 1ULL << shift; uint64_t m_2 = 1ULL << (shift >> 1); uint64_t b = ((y * m_2) << 1) + m; if (x >= b) { x -= b; y += m_2; } shift -= 2; } ``` 這個實作方法基本上是照著演算法的描述一步一步實現，可以看到他會存在一個乘法運算 #### 移除乘法運算 ```c int shift = (total_bits - 1 - clz64(x)) & ~1; uint64_t last = 0; while (shift >= 0) { m = 1ULL << shift; uint64_t m_2 = 1ULL << (shift >> 1); uint64_t b = last + m; last >>= 1; if (x >= b) { x -= b; y += m_2; last += m; } shift -= 2; } ``` 這個方法由一個 `last` 儲存每一次 `y` 更新時的 `m` 並在進入判斷式前右移一格這個調整仍是有效的原因，是因為所有 `m` 都是 2 的次方以此改寫公式 $$ (2^{i+k}+...+2^i+2^{i-j})^2=(2^i)^2+(2(2^{i+k}+...+2^i)+2^{i-j})\cdot 2^{i-j} $$ 再展開 $$ (2^i)^2+(2^{i-j})^2+2^{2i+k-j+1}+...+2^{2i-j+1} $$ 觀察到 $2^{2i-j+1}$ 可以發現只要對 $2^{2i}$ 右移 $j-1$ ，就能得到現在做計算所需的值這正是 `last` 在做的事情 #### 合併 `last` 與 `y` ```c int shift = (total_bits - 1 - clz64(x)) & ~1; while (shift >= 0) { m = 1ULL << shift; uint64_t b = y + m; y >>= 1; if (x >= b) { x -= b; y += m; } shift -= 2; } ``` 在 `shift` 為 $2i$ 加上一個 `m`: $2^{2i}$ 由於到迴圈結束時會被右移 $i$ 格，對最後的 `last` 而言相當於每次都加上 $2^i$ 這與 `y` 的功能完全相同到了這步基本上已經跟原本的 `sqrti` 相同，只差把每次重新計算的 `m` 放在迴圈外，每次 `m` 往右移兩格的調整 ### 向上取整 `x` 在計算過程會被減去 `y` 的平方若最後 `x` 不是 0 ，就代表 `x` 原本不是完全平方數，需要向上取整，也就是額外 `+1` 因此，可以對最後的 `return` 做修改 ```c return y + (x && 1); ``` 即可在只使用加減法與位元操作的情況下，完成向上取整的平方根 # 第二週測驗 3 ## 填空 - `AAAA`: `map->bits` - `BBBB`: `map->bits` - `CCCC`: `first->pprev` - `DDDD`: `n->pprev` - `EEEE`: `n->pprev` ## 程式碼解釋

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.