2024q1 Homework2 (quiz1+2)

contributed by < BooleanII >

Graphviz

佇列與串列的操作，單透過文字時常難以清楚描述，需要輔以圖示說明讓整個流程更加易懂，作業要求中提到使用 Graphviz 進行圖片繪製，以下為使用 Graphviz 的筆記。

Grpahviz 安裝 (under Ubuntu)

$ sudo apt install graphviz

Graphviz 提供多種 layout engine 繪製不同類型的圖片，甚至可以自行建立客製化的 layout engine 畫出自己想要的圖片風格，下列皆為同一組描述文字檔使用不同 layout engine 繪製的圖片。

graph G {
    a -- {b,c};
    b -- d;
    d -- {e,f};
}

Layout Engine	範例圖片
dot
neato
fdp
sfdp
circo
twopi
osag
patchwork

圖片內容以 .dot 檔進行描述，描述順序不影響繪圖結果，註解的語法除了 C 語言中的 // 和 /**/ 外，還多了 # 可以使用，其常用語法範例如下所示：

digraph abc {
    size ="4,4";
    main [shape=box]; /* this is a comment */
    main -- parse [weight=8];
    parse -- execute;
    main -- init [style=dotted];
    main -- cleanup;
    execute -- { make_string; printf}
    init -- make_string;
    edge [color=red]; // so is this
    main -- printf [style=bold,label="100 times"];
    make_string [label="make a\nstring"];
    node [shape=box,style=filled,color=".7 .3 1.0"];
    execute -- compare;
}

需注意使用 digraph 或 graph 進行描述的差異，一開始測試因為這個問題花了不少時間。前者的連線帶有箭頭，且連線的描述文字為 -> ，而後者的連線描述文字為 -- ，如混用則該文字檔進行編譯時系統會顯示 syntax error。

Error: test.dot: syntax error in line 14 near '->'

撰寫好描述文字檔後，需使用命令進行編譯產生圖片，命令格式如下：

cmd [ flags ] [ input files ]

透過 cmd 選擇要使用上面提到的那一個 layout engine 進行繪圖，並以 -Tpng 選擇輸出圖片格式為 png 檔、 -o filename 指定輸出圖檔名稱，範例如下：

dot test.dot -Tpng -o abc.png

參考文件

Graphviz 中文筆記
Drawing graph with dot

第 1 週測驗題

測驗 1

題目提到是使用 Optimized QuickSort — C Implementation (Non-Recursive) 的 Quick Sort 演算法進行修改，故先閱讀該網頁中的介紹，該演算法提出使用 L 與 R 紀錄需交換資料的指標，每次的 pivot run 排序流程如下：

1. 取串列的 head 作為 pivot
2. R 自串列末端節點開始，往串列的前一個節點移動，直到該節點的數值小於 pivot 時停止，將該節點的資料複製到 L
3. L 自串列起始節點開始，往串列的下一個節點移動，直到該節點的數值大於 pivot 時停止，將該節點的資料複製到 R
4. 重複步驟 2 到 3 直到 R 的位置比 L 更接近串列起始點
5. 將 L 的節點寫入 pivot 數值
6. 完成這一輪的排序
   

該作者表示其演算法的具備下列優缺點：

• [優] 使用 begin 與 end 儲存串列以取代遞迴呼叫，降低遞迴衍生的 function call 與 stack 成本
• [優] 減少排序過程中資料節點的移動次數
• [缺] 排序過程中需要較多次數比較

在測驗 1 題目描述中，說明作法是將 'L' 與 'R' 找出需要交換的數量，以範例的串列為例，取串列的 head 為 pivot ， L 應會紀錄到3筆小於 pivot 的節點，而 R 則紀錄到有2筆大於 pivot 的節點（題目解說需要修改）。

然而一開始無法將測驗的題目描述與提供的程式碼內容對應起來，以為 L 與 R 直接用於儲存需要交換的序列長度，但程式碼中將兩者宣告為 node_t 結構體，明顯並非單純紀錄數量。閱讀整份程式碼並對照 Optimized QuickSort — C Implementation (Non-Recursive) 後才慢慢想通。

題目的快速排序同樣使用第一筆資料做為 pivot ，但 L 與 R 的用途為標示待排序序列的起始點與末端點，而 begin 與 end 用於儲存尚未排列好的序列起始點與末端點，存入 stack 的順序如下：

1. 小於 pivot 的序列
2. pivot
3. 大於 pivot 的序列

每一輪的排序使用 begin 陣列中的最後一筆序列，在第一輪排序中，我們將 list 的開頭與末端分別放入 begin 和 end 中， list_tail 函式功能為走訪序列上的每一個節點，回傳 list 末端的 node 的指標。而在 quick_sort 函式中被呼叫的 list_length 函式與 list_tail 大同小異，同樣是以走訪每一個節點的方式計算序列的長度，故兩者皆透過下列程式碼將 left 指向序列中的下一個節點：

left = &((*left)->next)

p 節點指標用於走訪整個序列，將每個節點的值與 pivot 進行比較。因此，在 while 迴圈中， p 需要指向下一個節點，並執行 quick_sort 函式中最關鍵的部分：將小於等於 pivot 的節點存入 left 序列，大於 pivot 的節點存入 right 序列中。

while (p) {
    node_t *n = p;
    p = p->next;
    list_add(n->value > value ? &right : &left, n);
}

根據前述描述，將比較後的 left 與 right 序列分別存入 begin 和 end stack 中，由於 end 代表的是序列的末端點，可以透過呼叫 list_tail 函式取得，以下是存入 stack 的完整程式碼如下：

begin[i] = left;
end[i] = list_tail(&left);
begin[i + 1] = pivot;
end[i + 1] = pivot;
begin[i + 2] = right;
end[i + 2] = list_tail(&right);

當 stack 中的最後一筆序列的起始點與末端點為同一個節點時，表示該序列只包含一個已完成排序的節點。在這種情況下，我們可以將 stack 中的資料 pop 出來，並用 list_add 將它們加入 result 序列中。然後對 stack 中剩下的序列重複執行上述流程，以獲得排序完成的序列。

總結測驗 1 的答案如下：

1. AAAA = (*left)->next
2. BBBB = (*left)->next
3. CCCC = p->next
4. DDDD = list_tail(&left)
5. EEEE = list_tail(&right)

使用 Linux 核心風格的 List API 改寫上述程式碼

這邊以 lab0-c 作業中的結構體來進行實現。 node_t 可使用變形後的 element_t 結構體取代，將 value 成員的型態由 char * 改為 int ，沿用 list_head 結構體來達成 Linux 核心風格的佇列結構，並搭配 list.h 提供的佇列操作函式進行相關實作。

typedef struct {
    int value;
    struct list_head list;
} element_t;

儲存未排序佇列的 begin 與 end 兩個 stack ，因可利用 list_head 結構體中的 prev 指標，避免使用 list_tail 走訪整個佇列，以獲得佇列中的最後一個節點，並省去使用 end 儲存未排序的末端點。
因佇列的 head 並未儲存資料，故進行排序時將 head 移除，保留第一個資料節點的 prev 指向佇列中的末端點，佇列末端點的 next 指向 NULL ，使佇列變形為串列。修改後的 quick sort 程式碼如下：

while (i >= 0) {
    struct list_head *L = begin[i], *R;
    if (begin[i]) {
        R = begin[i]->prev;
    } else {
        R = NULL;
    }
    if (L != R) {
        struct list_head *pivot = L;
        pivot_value = list_entry(pivot, element_t, list)->value;
        struct list_head *p = pivot->next;
        pivot->prev = pivot;
        pivot->next = NULL;

        while (p) {
            struct list_head *n = p;
            p = p->next;
        // insert element into right value if element is larger than pivot
            list_add(list_entry(n, element_t, list)->value > pivot_value 
                      ? &right : &left, n);
        }

        begin[i] = left;
        begin[i + 1] = pivot;
        begin[i + 2] = right;

        left = right = NULL;
        i += 2;
    } else {
        if (L)
            q_list_add(&result, L);
      // pop stack
      i--;
    }
}

實作後發現為了使用 list_head 結構體中的 prev 成員儲存串列的末端點，程式碼較原本的版本多了好幾處的細節處理，如 R 需判斷當前的 stack 內容是否為 NULL ， list_add 函式也需針對輸入的串列指標是否指向 NULL 來決定 prev assign 的內容。

void list_add(struct list_head **list, struct list_head *node) {
    node->next = *list;
    if (*list) {
        node->prev = (*list)->prev;
    } else {
        node->prev = node;
    }
    *list = node;
}

對程式碼做些改進

在實際進行改進之前，我們先比較原始的程式碼和使用 List API 改寫後的版本。這兩個版本在不同資料量下使用 stack 的深度是相同的，因為它們僅僅是對資料結構的不同實作方式。此外，我們也需要留意到，對於相同資料量，shuffle 函式會產生相同的洗牌結果。因此，對於相同長度的資料，使用 shuffle 函式處理後進行測試，stack 的使用深度也將保持一致。

• 原始程式碼

$ ./opt_quicksort 
data size: 10, deepest level: 4
data size: 100, deepest level: 14
data size: 1000, deepest level: 26
data size: 10000, deepest level: 38
data size: 100000, deepest level: 48

• 使用 List API

$ ./quicksort_linklist 
data size: 10, deepest level: 4
data size: 100, deepest level: 16
data size: 1000, deepest level: 26
data size: 10000, deepest level: 40
data size: 100000, deepest level: 48

在 Linux 系統中，可以使用 clock 函式來獲取程式碼的執行時間，以檢測程式碼在不同的資料長度下的執行時間。請注意，這僅測量快速排序的執行時間，不包含 shuffle 的執行時間。以下是執行 100,000 次的平均結果，顯示使用 list API 實作的版本速度比原始程式碼更快。

• 原始程式碼

$ ./opt_quicksort 
Data size: 10, execution time: 0.000618 ms 
Data size: 100, execution time: 0.006516 ms 
Data size: 1000, execution time: 0.090552 ms 
Data size: 10000, execution time: 1.364948 ms 
Data size: 100000, execution time: 23.467461 ms

• 使用 List API

$ ./quicksort_linklist 
Data size: 10, execution time: 0.000518 ms
Data size: 100, execution time: 0.005165 ms
Data size: 1000, execution time: 0.069995 ms
Data size: 10000, execution time: 0.979346 ms
Data size: 100000, execution time: 14.678142 ms

以 1000 筆資料的排序條件下進行比較，使用 perf record 紀錄兩者執行 100000 次，所獲得的性能指標。從結果可發現原始程式碼雖然有較高的 IPC ，但實際執行時間卻比 List API 版本來的久。

Event	原始程式碼	使用 List API	Better
Cache misses	171757.2383	66258.646	List API
Cache references	401250.1308	64210.7886	原始程式碼
Branch misses	454205710.1405	42053879.6032	List API
Branches	8143817422.8188	8007732828.4409	List API
Instructions	95711793.1548	58791077.9339	原始程式碼
Cycles	36256592463.9717	27774658834.164	原始程式碼
Page faults	0	0	Same
CPU migration	3.9996	4
Context Switch	60.0038	26.9982	List API
Task clock	8815.5827	6417.4784	List API

當使用第一筆資料作為 pivot ，且資料是最已排序的或者是逆序排列時，就會導致最壞情況發生。這種情況下，快速排序的效率會降到最低，時間複雜度將達到

$O(n^2)$ 。這是因為在這種情況下，每次切割都只會將一個元素移到正確的位置上，而不是將資料均勻地分割為兩部分，造成每筆資料都會單獨存入 stack 中，使 stack 使用的深度將與資料長度相同。

• 對已排序資料進行排序

$ ./quicksort_linklist 
data size: 10, deepest level: 10
data size: 100, deepest level: 100
data size: 1000, deepest level: 1000
data size: 10000, deepest level: 10000
data size: 100000, deepest level: 100000

由上述的比較可看出待改進的點有二：

1. stakc 大小在 worst case 下，只需要 data size 的深度，此項改進可降低排序過程中的記憶體需求。
2. 透過 pivot 的選擇必免 worst case 。常見的作法為從序列中隨機選擇 pivot 。

測驗 2

Timsort演算法主要行為是將序列中已完成排序的部份切割為子序列（ run ），當 run 的滿足特定條件時，使用合併排序（ merge sort ）將兩個 run 進行合併。
在題目解說中，有提到『合併序列時，若 run 的數量等於或者略小於 2 的冪，效率會最高；若略大於 2 的冪，效率就會特別低。』。乍看之下不是很懂哪個要略小於 2 的冪才能獲得較高效率，是指 minrun 的長度還是切割後 run 的數量？

參考維基百科的介紹進行整理：
Timsort 運作時會定義最一開始切割的每個 run 最小長度為 minrun ，切割時當已排序的 run 長度不足 minrun 時，會將方的資料節點以 insertion sort 方式插入，使該 run 長度滿足 minrun 。

切割完 run 後， Timsort 會使用合併排序將兩個 run 合併為一個 run ，而要將哪兩個 run 進行合併則依據 run 的長度，以下列關係式進行決定。當 XYZ 三個 run 之間無法滿足關係式時， X 與 Y run 會進行合併。

• $Z>Y+X$
• $Y > X
  (e.g. Z 的長度小於 Y+X ，則 X 與 Y 會進行合併)
  
  

因 Timesort 為 stable sorting 演算法（同樣大小的節點的順序在排序後不變），為了在時間與空間成本上達到平衡，在合併 run 時只變更兩個 run 間需要合併的範圍。

首先， Timsort 會搜尋 Y run 中的第一個節點在 X run 中合併時要插入的位置，接著搜尋 X run 中末端節點合併入 Y run時要插入的位置。合併時僅對這兩個插入點之間的節點進行操作，節省 merge 時所需使用的暫存記憶體空間。

維基百科引述下列連結文章，指出當 run 的數量小於或等於 2 的冪時，在合併階段可以得到較好的效率，降低 run 在合併時因長度落差過大造成的效率降低問題。

https://hg.python.org/cpython/file/tip/Objects/listsort.txt

名詞定義
minrun ：run的最小分割長度
N ：序列資料總數
n ：切割後的 run 長度

測驗題目的 timsort 在合併時不需 malloc 暫存記憶體空間 (in-place algorithm) ，共分為六個函式進行實作，為了統計排序過程中比較次數，在每個函式輸入 priv 的 void 指標，用來傳遞並累加比較次數的參數 count 。

• find_run
• merge_collapse
• merge_force_collapse
• build_prev_link
• merge_final

需注意題目的比較節點資料大小的方式，有別於直接使用 if 判斷式，而是透過呼叫 輸入參數的 cmp 的函式指標，以函式 compare 進行比較，增加整體程式碼的靈活度(如透過呼叫不同的 compare 函式決定排序的方向為 descend 或 ascend ）。

int compare(void *priv, const struct list_head *a, const struct list_head *b)
{
    if (a == b)
        return 0;

    int res = list_entry(a, element_t, list)->val -
              list_entry(b, element_t, list)->val;

    if (priv)
        *((int *) priv) += 1;

    return res;
}

首先使用 find_run 函式進行串列的 run 切割，當發現到資料串列中存在降序排列時，會將該節點切割放入 prev 串列中，放入的過程中會進行反轉使其成為升序排列；如資料為升序排列時，則會繼續走訪下一個節點，直到出現降序排列時停止。這個切割方法未如同傳統 timsort 演算法介紹中提到的使用特定 minrun 大小進行切割，是後續可以進行改進的地方。

切割好的 run 串列透過 pair 結構體的 head 成員進行儲存，並回傳至作為 stack 使用的 tp 串列，而剩餘尚未切割的串列則儲存於 next 成員中。需注意 find_run 切割時未處理節點的 prev 指標內容，僅將 run 長度儲存於該 run 串列中第二個資料節點的 prev 進行儲存 （ head->next->prev )。

struct pair {
    struct list_head *head, *next;
};

以下圖串列 [8,11,9,7,5] 為例

共可被切割為兩個 run ：

並依序存入 tp stack 中：

在此測驗的程式碼中區分了好幾種合併的函式，當每完成一個 run 切割，皆會呼叫一次 merge_collapse 函式，如 stack 中的 run 長度滿下列條件就進行合併。

• tp stack 中有三個以上的 run ， tp->prev->prev 的長度小於等於 tp->prev 與 tp 的總和
• tp stack 中有四個以上的 run ， tp->prev->prev->prev 的長度小於等於 tp->prev->prev 與 tp->prev 的總和
• tp stack 中有兩個 run ，且 tp->prev 中的長度小於等於 tp

merge_collapse 函式的合併是使用 merge 函式進行，為實現 in-place algorithm ， merge 函式未 malloc 暫存的記憶體空間，而使用間接指標 **tail 來達成資料合併。該操作手法可以參照 你所不知道的 C 語言：指標篇 ，以間接指標 tail 指向當前完成合併的串列末端點，故在最一開始的時候應指向回傳合併串列的 head ，將 tail assign 為 ＆head 儲存 head 的位址。

struct list_head *head;
struct list_head **tail = &head;

完成比較後，將 *tail assign 為較小的資料節點指標，使 head 指向 a 或 b 串列中最小的節點，並將 tail assign 為該資料節點結構體中的 next 成員，讓 *tail 在下一次比較中可指向次小的節點，不斷執行到其中一方的串列走訪完畢時，將 *tail assgin 剩餘的串列。

for (;;) {
    /* if equal, take 'a' -- important for sort stability */
    if (cmp(priv, a, b) <= 0) {
        *tail = a;
        tail = &(a->next);
        a = a->next;
        if (!a) {
            *tail = b;
            break;
        }
    } else {
        *tail = b;
        tail = &(b->next);
        b = b->next;
        if (!b) {
            *tail = a;
            break;
        }
    }
}

當輸入串列完成所有的 run 切割後，呼叫 merge_force_collapse 函式將 stack 中所有的 run 兩兩進行合併，直到 stack 中的 run 數量小於三個才停止，此處看起來是個可以改進的地方，如果能夠將所有 run 在此函式中完成合併，若 stack 中只剩兩個 run 時，後續就不用額外使用 merge_final 函式進行合併。

最後，要注意因先前的串列操作皆未對 list_head 結構體中的 prev 指標進行處理，故完成排序後透過 build_prev_link 函式，將 prev 重新寫入正確的指向節點，並在最後將 tail->next 需指向 head ，而 head->prev 需指向 tail讓整個排序好的串列可回到 Linux 風格的環狀佇列架構。

static void build_prev_link(struct list_head *head,
                            struct list_head *tail,
                            struct list_head *list)
{
    tail->next = list;
    do {
        list->prev = tail;
        tail = list;
        list = list->next;
    } while (list);

    /* The final links to make a circular doubly-linked list */
    tail->next = head;
    head->prev = tail;
}

因為 build_prev_link 函式是在完成所有 run 的合併後才能執行，故 timsort 函式最後的 if 判斷式數值應為 1 。

if (stk_size <= 1) {
    build_prev_link(head, head, stk0);
    return;
}

總結測驗 2 的答案如下：

1. AAAA = &head
2. BBBB = &(a->next)
3. CCCC = &(b->next)
4. DDDD = tail->next
5. EEEE = head->prev
6. FFFF = 1

第 2 週測驗題

測驗 1

測驗 2

測驗 3

題目為實作 find_nth_bit 函式，讓其可在連續的記憶體空間找出第 N 個設定的位元。由於直接從 find_nth_bit 開始看程式碼看不太懂運作原理，故先從此函式的的程式碼最終會使用到 __ffs 開始說明。

__ffs 用於找出輸入的 word 中哪個位元是第一個為 1 的位元（由最低有效位元 Least Significant Bit 開始找）。 __ffs 函式使用 binary search 方式進行實作，透過 bit mask 確認右半邊的位元是否皆為零，若皆為零則將輸入的數值向右位移，搜尋剩下的另外一半位元。以 64 bit 長度的 word 為例，使用 '0xffffffff' 的 bit mask 確認右半邊的 32 bit 資料是否皆為0，若成立則將位置變數 num 累加 32 ，並將 word 向右位移 32 bit ，接續確認剩餘的 32 bit 資料。需注意此函式如果輸入的 word 內容為 0 時，輸出結果會是錯誤的 63 。

static inline unsigned long __ffs(unsigned long word)
{
    int num = 0;

#if BITS_PER_LONG == 64
    if ((word & 0xffffffff) == 0) {
        num += 32;
        word >>= 32;
    }
#endif
    if ((word & 0xffff) == 0) {
        num += 16;
        word >>= 16;
    }
    if ((word & 0xff) == 0) {
        num += 8;
        word >>= 8;
    }
    if ((word & 0xf) == 0) {
        num += 4;
        word >>= 4;
    }
    if ((word & 0x3) == 0) {
        num += 2;
        word >>= 2;
    }
    if ((word & 0x1) == 0)
        num += 1;
    return num;
}

接續來看有呼叫 __ffs 的 fns 函式，其功能為找出輸入的 word 中，第 'n' 個為 1 的位元位置，注意這裡的 n 是由 0 開始數，當 n 的數值非零時，代表 __ffs 找到的位元位置被非所要的位置，要將該位元設為 0 ，重新執行 __ffs 找到下一個為 1 的位置。以函式輸入 word 為 5 、 n 為 1 ，其輸出結果應為 2 。

fns 中使用 __clear_bit 函式進行上述將 word 特定位元設為 0 的實做，由於 find_nth_bit 函式的功能需能用在連續記憶體空間中，故這邊使用指標處理當指定的位元位置超出一個 long 的長度時的狀況，並在最後以BIT_MASK 函式獲得的 bit mask 將目標的位元設為 0 。需注意由於是將目標位元設為 0 ，故在與 *p 做 ＆ 處理前需將 bit mask 取 not 運算。

static inline void __clear_bit(unsigned long nr, volatile unsigned long *addr)
{
    unsigned long mask = BIT_MASK(nr);
    unsigned long *p = ((unsigned long *) addr) + BIT_WORD(nr);

    *p &= ~mask;
}

接續看到 small_const_nbits 巨集( macro )，當中用到 gcc 提供的 built-in function __builtin_constant_p ，該函式的功能是讓 gcc 在編譯時檢查輸入的參數（ argument ）是否為常數，若 gcc 無法在優化選項的條件下判斷其為常數則回傳為 0 ，反之則回傳 1 代表確定是常數。故該函式僅有在 nbits 同時滿足大於零、小於等於 long 長度且 gcc 判斷為常數時回傳為 1 。故當 find_nth_bit 要找尋的資料範圍大於一個 long 長度時，將使用 FIND_NTH_BIT 找處第 N 個為 1 的位元位置。

#define small_const_nbits(nbits) \
    (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG && (nbits) > 0)

GENMASK 巨集因涉及到了 bitwise 操作，透過直接帶入數字實驗很快就能抓到邏輯，該巨集的作用為建立指定區間為 1(set) 的 bit mask ， h 作為 head 決定最後一個為 set 的位元， l 作為 last 決定第一個為 set 的位元。其運作的原理首先透過 ~0UL 獲得 0xFFFF FFFF FFFF FFFF ，將 ~0UL 減去 1ul向左位移 l 後的數值，使 l 位元設定為 0 ，在透過加 1 讓較 l 低的位元設定為 0 ；而透過向右位移 ~0UL 可讓較 h 高的位元設為 0 ，使用 h 與 l 分別產生的兩個 bit mask 取 ＆ 獲得兩者皆為 1 的位元 bit mask。

以 long 為 64 bits 的電腦為例，當 h 為 15 、 l 為 4 時， GENMASK 的輸出為 0x0000 0000 0000 FFF0 。此巨集在 find_nth_bit 函式中，用於限制 fns 搜尋的範圍，避免 find_nth_bit 回傳超出 size 參數範圍的結果。

再來看到 FIND_NTH_BIT 巨集實作所使用的 hweight_long 巨集，接連使用 __const_hweight64 、 __const_hweight32 、 __const_hweight16 和 __const_hweight8 組成，由呼叫的方式可推測以 byte 為單位，逐步擴展到 64 bits 的運算。

#define __const_hweight8(w)                                              \
    ((unsigned int) ((!!((w) & (1ULL << 0))) + (!!((w) & (1ULL << 1))) + \
                     (!!((w) & (1ULL << 2))) + (!!((w) & (1ULL << 3))) + \
                     (!!((w) & (1ULL << 4))) + (!!((w) & (1ULL << 5))) + \
                     (!!((w) & (1ULL << 6))) + (!!((w) & (1ULL << 7)))))

#define __const_hweight16(w) (__const_hweight8(w) + __const_hweight8((w) >> 8))
#define __const_hweight32(w) \
    (__const_hweight16(w) + __const_hweight16((w) >> 16))
#define __const_hweight64(w) \
    (__const_hweight32(w) + __const_hweight32((w) >> 32))

從最底層的 __const_hweight8 原理開始解說，此巨集最巧妙的地方在於連續使用兩次 not 的邏輯運算，非零的數值經過兩次 not 邏輯運算後結果皆為 true ( 1 )，再透過搭配 bit mask 可以計算該 byte 中為 1 的位元數量，並以此為基礎擴充到可計算 64 bits 長度資料中為 1 的位元數量。

接續解說 BITMAP_LAST_WORD_MASK ，其功能為列出最低位元 nbits 皆為 1 的 bit mask。以byte 長度的 bit mask 為例， nbits 為 1 時結果為 0x01 ； nbits 為 3 時結果為 0x07 。

回到 FIND_NTH_BIT 巨集，其輸入共有 FETCH 、 size 、 num 三個參數，傳入的資訊如下：

• FETCH ：搜尋記憶體空間的起點位址
• size ：搜尋的記憶體空間範圍，單位為 bit
• num ：第 num 個為 1 的位元

FIND_NTH_BIT 巨集的關鍵為下列 for 迴圈， idx 用於決定搜尋的記憶體 index 位置，當 idx 為 0 ，搜尋的記憶體位址為 FETCH ；當 idx 為 1 時，搜尋的記憶體位址為 FETCH+1 。故在 for 迴圈中的結束判斷條件中，使用當 idx 指到的記憶體位置超出搜尋範圍 size 大小時，則終止 for 迴圈的執行。

unsigned long sz = (size), nr = (num), idx, w, tmp;

for (idx = 0; (idx + 1) * BITS_PER_LONG <= sz; idx++) {
    if (idx * BITS_PER_LONG + nr >= sz)
        goto out;

        tmp = (FETCH);
        w = hweight_long(tmp);
    if (w > nr)
        goto found;

    nr -= w;
}

在該 for 迴圈中，每當呼叫 hweight_long 獲得當前記憶體位置的資料中為 1 的位元數量後，會將 num 數值減去該結果，代表還剩下多少個為 1 的位元尚未找尋到。

使用 goto 決定該巨集輸出的結果，第一個 if 判斷式將搜尋為 1 的位元數量納入是否要離開 for 迴圈的判斷依據。以 idx 為 0 時來看，當搜尋為 1 的位元數量大於等於搜尋的記憶體位元長度時， 代表需要搜尋為 1 的位元數量已超出所設定的搜尋範圍，故使用 goto 跳躍到 out 程式位置直接回傳 size 數值。反之，則使用 hweight_long 獲得當下記憶體內容中為 1 的位元數量，如大於目標搜尋數量，則代表該位址中存在搜尋的目標位元，使用 goto 跳躍到 found 程式位置，以 fns 找出並回傳位元的位置。需注意此處使用 min 比較 fns 計算結果與 size 哪個比較小後決定實際的輸出結果，主要是當 fns 未找到目標位元時，會回傳 BITS_PER_LONG ，透過 min 可限制 FIND_NTH_BIT 回傳的數值最大為 size 。

sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);

需注意當 size 非 64 bits 的倍數時，需要額外透過下列程式碼進行處理，透過 BITMAP_LAST_WORD_MASK 將超出 size 範圍的位元設為 0 ，避免後續的 fns 將其算入，故 CCCC 的答案為 < 。

if (sz < BITS_PER_LONG)
    tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);

最後提出我對這段程式碼感到疑惑且驚訝的地方，FIND_NTH_BIT 在 find_nth_bit 函式中以 addr[idx] 作為第一個輸入參數，使 FIND_NTH_BIT 在 idx 大於 0 時，可以透過 addr[idx] 讓 tmp assign 超出 64 bits 範圍的資料，這是我第一次看到的操作方式，這部份應該是 preprocessor 方面的語法應用，後續會花時間進行研究。

總結測驗 3 的答案如下：

1. AAAA = 0xffffffff
2. BBBB = ~mask
3. CCCC = <