# 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)
- 圖為隨機執行 alloc / free 1000000 次所花費的時間累積圖
- 如圖，目前的分配器效能明顯比 malloc 差
使用 perf 尋找效能瓶頸
- 可以發現 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 發生有關
### 嘗試減少 `find_free_tree` 使用
- 參考 [`rota1001` 開發紀錄](https://hackmd.io/@rota1001/linux2025-homework2#%E6%B8%AC%E9%A9%97-2)
效能或許有些微提昇，使用 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`
## 程式碼解釋
Sign in with Wallet
Connect another wallet