## 測驗 $\alpha -1$
解釋上述程式碼運作原理

* st_rotate_left

digraph st_rotate_left {
    graph [center=true, margin=0.01, nodesep=0.1, ranksep=0.2, width=2,ratio=.25];
    node [fontname="Courier New",color="0.0 0.0 0.0",fixedsize=true,width=0.6,shape=circle,label="",fontsize="20"];
    node [margin=0.02,fillcolor="lightgrey"];
    edge [dir=none];
    node [fillcolor="black"];
    graph [style=invis];

    subgraph cluster_Lower {
        Lower[label = "p"];
        LowerL[label = "n"];
        LowerM [style=invis];
        LowerR [style=invis];
        Lower -> LowerR [weight=100 style=invis];
        Lower -> LowerM [weight=100 style=invis];
        Lower -> LowerL;
        LowerLL[label = "l"];
        LowerLM [style=invis];
        LowerLR [style=invis];
        LowerRM [style=invis];
        LowerRR [style=invis];
        LowerLLL[style=invis];
        LowerLLM[style=invis];
        LowerLLR[label = "l_r"]
        LowerL -> LowerLR [weight=100 style=invis];
        LowerL -> LowerLL ;
        LowerL -> LowerLM [weight=100 style=invis];
        LowerR -> LowerRR [style=invis];
        LowerR -> LowerRM [weight=100 style=invis];
        LowerLL ->LowerLLL[weight=100 style=invis];
        LowerLL ->LowerLLM[weight=100 style=invis];
        LowerLL ->LowerLLR
    }
    node [fillcolor="red"];
    subgraph cluster_Upper {
        Upper[label = "p"];
        UpperL[label = "l"];
        UpperM [style=invis];
        UpperR [style=invis];
        UpperRM [style=invis];
        UpperRR [style=invis];
        Upper->UpperL;
        Upper->UpperM[weight=100 style=invis];
        Upper->UpperR[style=invis];
        UpperLL[style=invis];
        UpperLM[style=invis];
        UpperLR[label = "n"];
        UpperR->UpperRM[style=invis];
        UpperL->UpperLL[style=invis];
        UpperL->UpperLM[style=invis];
        UpperL->UpperLR;
        UpperRRR[label = "l_r"];
        UpperRRL[style=invis];
        UpperRRM[style=invis];
        UpperLR->UpperRRL[style=invis];
        UpperLR->UpperRRR;
        UpperLR->UpperRRM[style=invis];
    }

}

## 測驗 $\alpha -2$
撰寫時間量測程式碼

1. 引入資料結構 ```timespec```，實作計算時間消耗的函示 ```diff_in_second```：

struct timespec start, end;
double cpu_time1, cpu_time2;

static double diff_in_second(struct timespec t1, struct timespec t2)
{
    struct timespec diff;
    if (t2.tv_nsec-t1.tv_nsec < 0) {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec - 1;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec + 1000000000;
    } else {
        diff.tv_sec  = t2.tv_sec - t1.tv_sec;
        diff.tv_nsec = t2.tv_nsec - t1.tv_nsec;
    }
    return (diff.tv_sec + diff.tv_nsec / 1000000000.0);
}

2. 量測 insert 與 remove 消耗時間：

clock_gettime(CLOCK_REALTIME, &start);
for (long int j = 0; j < num; ++j) {
    treeint_insert(rand() % (num - 1));
}
clock_gettime(CLOCK_REALTIME, &end);
t1 = diff_in_second(start, end);

其中 ```num``` 為需要 insert/remove 的節點總數。對應 remove 的部分：

clock_gettime(CLOCK_REALTIME, &start);
for (long int k = 0; k < num; ++k) {
    int v = rand() % (num - 1);
    treeint_remove(v);
}
clock_gettime(CLOCK_REALTIME, &end);
t2 = diff_in_second(start, end);

3. 使用 numpy 與 matplotlib 繪製結果：

import numpy as np
import matplotlib .pyplot as plt

if __name__ == "__main__":
    output = np.loadtxt('data.txt', dtype='float').T

    X = output[0]
    fig, ax = plt.subplots(1, 1, sharey=True)
    ax.set_title('Time consumption', fontsize=16)
    ax.set_xlabel('numbers of insert/remove', fontsize=16)
    ax.set_ylabel('time (s)', fontsize=16)

    ax.plot(X, output[1], marker='+', markersize=3, label='insert')
    ax.plot(X, output[2], marker='*', markersize=3, label='remove')
    ax.legend(loc='upper left')

    plt.show()

4. 實驗結果：
* 硬體設備資訊

MacBook Pro (16-inch, 2019)
處理器：2.3 GHz 8 核心 Intel Core i9


## 測驗 $\beta -1$
觀察數值為 2 的冪的倍數時，其二進為表示法的最低 $n-1$ 的位元為 0。因此數值 $x$ 以 2 的冪做向上對齊時 (align up)，考慮以下情況：

1. 120 已經是 ```align_up(120, 4)``` 的結果。
2. 121 做完 ```align_up(121, 4)``` 後為二進位 11111<font color="#f00">00</font>，既然是向上對齊，考慮加上對齊值 $2^n$ ，然後對對齊值低於 $n$ 的位元遮蔽：

4. ```(122 + 4) &~ (4-1) = 124```
5. ```(123 + 4) &~ (4-1) = 124```
6. ```(124 + 4) &~ (4-1) = 128```，然而 124 做 align_up(124, 4) 是 124。觀察 124 + 4 的二進位，其第 2 位元發生進位，為避免此情況，改寫為 `(124 + (4-1)) &~ (4-1) = 124`

完整程式碼：

#include <stdint.h>

static inline uintptr_t align_up(uintptr_t sz, size_t alignment)
{
uintptr_t mask = alignment - 1;
if ((alignment & mask) == 0) { /* power of two? */
return (((sz) + (mask)) & ~(mask));
}
return (((sz + mask) / alignment) * alignment);
}

## 測驗 $\gamma -1$