2024q1 Homework1 (lab0)

1. 第 1 週所有教材及作業描述，啟發和疑惑

教材內容皆以引用符號表示，如下

引用內容

一、解讀計算機編碼

模除和溢位

無論在圓環上繞幾圈，最終的落點仍會在圓環上，每繞一圈就會發生最高位的溢位，並從 00000000 開始，這就是模除的本質。對於乘法，這個圓環依然使用，兩個數相乘，只要有一個數是正數，那麼就可用上述的圓弧不斷拼接來得到答案，比如 3 * 2 就是用 2 個 3 這個圓弧拼接兩次，-2 * 4 就是拿 4 個 -2 這個圓弧拼接四次，對於兩個負數相乘，比如 (-a) * (-b)，可拆成 (a * b) * (-1) * (-1)，於是只要計算 (-1) * (-1) 即可，也就是 11111111 * 11111111，最終的結果是 [xxx]00000001，高位全部溢位，結果就是正數 1。

(-a) * (-b)，可拆成 (a * b) * (-1) * (-1)，於是只要計算 (-1) * (-1) 即可，-1若用8位元表示即為11111111，因此a或b無論多小經過此算式皆會被進位置超出範圍被捨棄，因此只要計算(-1) * (-1) 即可，也就是 11111111 * 11111111，最終的結果是 [xxx]00000001，高位全部溢位，結果就是正數 1。也示範了負負何以得正。

阿貝爾群及對稱性

伽羅瓦的思想大致是：每個多項式都對應於一個與它的根的對稱性有關的置換群，後人稱之為「伽羅瓦群」。下圖是個簡單置換群
$S_{3}$ 的例子。一個方程有沒有根式解，取決於它的伽羅瓦群是否為可解群。

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

在上圖的置換群 S3 中，給定 3 個字母 ABC，它們能被排列成如上圖右邊的 6 種不同的順序。也就是說，從 ABC 產生 6 種置換構成的元素。這 6 個元素按照生成它們的置換規律而分別記成 (1), (12), (23) … 括號內的數字表示置換的方式，比如 (1) 表示不變，(12) 的意思就是第 1 個字母和第 2 個字母交換等等。

(12) 乘以 (123) 得到 (13) (原始為 ABC，先經過後者123之操作變為 BCA，再經過前者12之操作變為 CBA，即等同13) ，而當把它們交換變成 (123) 乘以 (12) 時，卻得到不同的結果 (23) (原始為 ABC，先經過後者12之操作變為 BAC，再經過前者123之操作變為 ACB，即等同23) ，因此，

S_{3}

是種不可交換的群，或稱之為「非阿貝爾群」。

S_{3}

不是循環群，也不是 (非循環) 交換群但為可解群(詳見 P.2-4)。

x 和 -x 在時鐘上的表示
問題:

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

和阿貝爾群對稱不同，0000 的一補數對稱是 1111，而非是本身，因此它的對稱軸線與阿貝爾群對稱軸線有偏差：

Image Not Showing Possible Reasons
The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted
Learn More →

此圖藍色是一補數的對稱軸，紅色是二補數的對稱軸

敘述中:「對稱軸線與阿貝爾群對稱軸線有偏差」，應該是藍色實線與紅色實線之偏差，那藍色虛線為何?

常數時間實作
如何移除 branch (即 "branchless") 呢？

a b s (x) = {\begin{cases} x & if x \geq 0 \\ - x & if x < 0 \end{cases}

By 2's complement

a b s (x) = {\begin{cases} x & if x \geq 0 \\ (\sim x) + 1 & if x < 0 \end{cases}

再透過Bitwise XOR (^)

bit a	bit b	bitwise `^`
0	0	0
1	0	1
0	1	1
1	1	0

最後兩行可看出無論a為正或負，可給定b而得到異號a (以此達成反轉) ，利用此特性得到以下branchless程式碼

int32_t abs(int32_t x) {
    int32_t mask = (x >> 31);
    return (x + mask) ^ mask;
    // or return x ^ mask - mask; // 因反轉異號
}

首先，令 mask 為 x 算術右移31位，此時若 x 為正，mask 為 0x00000000 ， x 為負則為 0xFFFFFFFF ，最後就可利用上述數學式轉換。

反轉 : 若 x 為負， mask 為 0xFFFFFFFF ，以此可達成反轉，若 x 為正， mask 為 0x00000000 ，可以避免不必要的反轉。
減1 : 2's complement 重要之處，0xFFFFFFFF 即為 -1 ， 0x00000000 即為 0 ，因此 + mask 即使 x 為正，也因為mask 為 0 而不影響。

最後達成branchless，無須因為應付不同狀況去產生branch，同時使用bitwise的操作達成高效。
不過，當 x 為

- 2^{31}

時 (10000000000000000000000000000000) ，其所轉換的

2^{31}

再2補數中是不存在的，因此會變為 01111111111111111111111111111111 再加上 1 超出正值上限進而變回

- 2^{31}

，因此使用此 abs 須保證傳遞參數之有效範圍。

二、你所不知道的C語言：指標篇

沒有「雙指標」只有「指標的指標」

void func(int *p) { p = &B; }

在這裡因為單純修改指標的值，也就是複製一份 ptrA 並指向 B 之位址，並不是從根本去修改 ptrA ，因此 ptrA 不會有任何改變。

若要從根本去修改，便應該從指標 ptrA 之位址下手，如下

void func(int **p) { *p = &B; }

函式 func 複製一份指向 ptrA 之位置，並更改指向 ptrA 指向的位置之值。

Pointers vs. Arrays

array vs. pointer

in declaration

extern, 如 extern char x[];
$\to$ 不能變更為 pointer 的形式

definition/statement, 如 char x[10]
$\to$ 不能變更為 pointer 的形式

parameter of function, 如 func(char x[])
$\to$ 可變更為 pointer 的形式
$\to$ func(char *x)

in expression

array 與 pointer 可互換
x[i] 總是被編譯器改寫為 *(x + i)
$\leftarrow$ in expression
int main() {
    int x[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    printf("%d %d %d %d\n", x[4], *(x + 4), *(4 + x), 4[x]);
}
array subscripting 在編譯時期只確認以下兩件事:

得知 size

取得陣列第 0 個 (即最初的一項) 元素的指標

前兩者以外的操作，都透過 pointer

array subscripting => syntax sugar

Function Pointer

int main() { return (********puts)("Hello"); }

function designator - 基本上就是 function name

無論函式名稱 (此為 puts ) 加上多少個 * ，他仍是一個 function designator ，最後被轉為 pointer to function returning type ，所以 * 的數目不會影響結果。

Address and indirection operators

[] or * 的操作結果：跟這兩個作用時，基本上就是相消

* - operand 本身

[] - & 會消失，而 [] 會被轉換成只剩 + (註：原本 [] 會是 + 搭配 *)

例如: &(a[5]) == a + 5
char str[123];
為何 str == &str 呢？

實際上左右兩邊的型態是不一樣的，只是值相同。

左邊的是 pointer to char：char *

規格書中表示：除非遇到 sizeof 或是 & 之外，array of type (在這就是指 str) 都會被直接解讀成 pointer to type (在這就是 pointer to char)，而這個 type 是根據 array 的第一個元素來決定的。

右邊的則是 pointer to an array： char (*)[123]

上面提到：遇到 & 時，str 不會被解讀為 pointer to type，而是做為原本的 object，在這就是 array object，而 address of array object 也就是這個 array object 的起始位址，當然也就會跟第一個元素的位址相同。

重新探討「字串」

由於 C 語言提供了一些 syntax sugar 來初始化陣列，這使得 char *p = "hello world" 和 char p[] = "hello world" 寫法相似，但底層的行為卻大相逕庭

背景知識: 你所不知道的 C 語言：函式呼叫篇關於 stack 的描述

以指標的寫法 char *p 來說，意思是 p 將會是指向 static storage 的一個指標。如此的寫法有潛在問題，因為當開發者嘗試修改 string literals 的內容，將會造成未定義行為，而編譯器並不會對存取 p 的元素提出警告

值得注意的是，陣列的寫法依據 C99 規範，string literals 是必須放在 "static storage" 中，而 char p[] 的語意則表示要把資料分配在 stack 內，所以這會造成編譯器 (gcc) 隱性地 (implicitly) 產生額外的程式碼，使得 C 程式在執行時期可把 string literals 從 static storage 複製到 stack 中。雖然字串本身並非存放於 stack 內，但 char p[] 卻是分配在 stack 內，這也造成 return p 是未定義行為

如果是用 char p[]的方法，直接印出p是可以的，但如果是要return就會出錯，因為一離開函式該空間便會被清除。

使用函式回傳字串
在C語言，要回傳字串還是只能用全域變數或靜態修飾宣告，強制將記憶體位置放置不會被free掉的地方。否則在離開函式copystr()的時候就，宣告char *a會free掉, 回傳的位址指向的東西將是一串無意義的東西。

若使用char *p = "hello world"話，只要不改他就不會出現這個問題，但他的問題是literals不能改值。因此建議改用const char * p = "hello world" ，如此一來便無法改動 p 指向位址之值。

C 語言 offsetof 巨集的定義

<stddef.h> 定義了 offsetof 巨集，取得 struct 特定成員 (member) 的位移量。傳統的實作方式如下:
#define offsetof(st, m) ((size_t)&(((st *)0)->m))
這對許多 C 編譯器 (像是早期的 gcc) 可正確運作，但依據 C99 規格，這是 undefined behavior。後來的編譯器就不再透過巨集來實作，而改用 builtin functions，像是 gcc:
#define offsetof(st, m) __builtin_offsetof(st, m)
這對於 C++ 非常重要，否則原本的巨集連編譯都會失敗。

延伸閱讀: C99 的 offsetof macro

Linux 核心延伸 offsetof，提供 container_of 巨集，作為反向的操作，也就是給予成員位址和型態，反過來找 struct 開頭位址：
#define container_of(ptr, type, member) ({ \
    const typeof(((type *) 0)->member) *__mptr = (ptr); \
    (type *) ((char *)__mptr - offsetof(type,member) );})

因此，可透過此程式碼找出組合的 struct 之位置，如下
此次lab0作業

typedef struct {
    char *value;
    struct list_head list;
} element_t;

struct list_head {
    struct list_head *prev;
    struct list_head *next;
};

struct element_t 中的成員 list 為 struct list_head ，其成員 *prev 及 *next 皆為指向 struct list_head 之指標，也就是無法只向下一個 struct element_t ，此時若利用 container_of ，可串接這兩個 struct ，並利用指向的 struct list_head (相當於 struct element_t 中的成員 list 之位置) ，反向尋找出 struct element_t 之位置。

三、你所不知道的 C 語言: linked list 和非連續記憶體

從 Linux 核心的藝術談起

void remove_list_node(List *list, Node *target)
{
    Node *prev = NULL;
    Node *current = list->head;
    // Walk the list
    while (current != target) {
        prev = current;
        current = current->next;
    }
    // Remove the target by updating the head or the previous node.
    if (!prev)
        list->head = target->next;
    else
        prev->next = target->next;
}

直觀的寫法會有特例，也就是第一筆資料與中間的資料的移去操作不同。
若要移去的是第一筆資料，那就需要把指標指向第一個節點；而若是要移除中間的資料，則須要把指標指向目標的前一個節點。

void remove_list_node(List *list, Node *target)
{
    // The "indirect" pointer points to the *address*
    // of the thing we'll update.
    Node **indirect = &list->head;
    // Walk the list, looking for the thing that 
    // points to the node we want to remove.
    while (*indirect != target)
        indirect = &(*indirect)->next;
    *indirect = target->next;
}

Linus Torvalds 換個角度來思考，通過指標的指標 (或稱「間接指標」，即 indirect pointer) 來操作，如此一來，上面的特例就不存在。

第一個方法為檢測指向的值是否正確，因此需要一個額外的指標去保留，當要移除時需判別是否為第一個再去決定將什麼指標重接。
第二個方法是利用指標之指標，這樣實際上之指標會為在上一個指標所指向的 node ，即上一個 node ，因此無須因為是否為 head 而去使用不同方法。

void append(int value, list_entry_t **head)
{
    list_entry_t *direct = *head;
    list_entry_t *prev = NULL;

    list_entry_t *new = malloc(1 * sizeof(list_entry_t));
    new->value = value, new->next = NULL;

    while (direct) {
        prev = direct;           
        direct = direct->next;
    }

    if (prev)
        prev->next = new;
    else
        *head = new;
}

函式的參數列表中，之所以用 list_entry_t **head，而非 list_entry_t *head，是因為原本傳入的 head 可能會被變更，但 C 語言在參數傳遞時永遠都是傳遞數值 (副本)，於是若接受 list_entry_t *head 做為參數，那就要提供 append 函式的傳回值，也就是說，該函式原型宣告變為:

list_entry_t *append(int value, list_entry_t *head);

或運用 indirect pointer 的技巧:

void append_indirect(int value, list_entry_t **head)
{
    list_entry_t **indirect = head;

    list_entry_t *new = malloc(1 * sizeof(list_entry_t));
    new->value = value, new->next = NULL;

    while (*indirect)
        indirect = &((*indirect)->next);

    *indirect = new;
}

如果在函數內部修改 head 指標的值，即讓它指向新的 linked list 頭部，這個修改僅在函數內部有效，不會影響外部。為了在函數內部修改外部傳入的指針，需要使用 list_entry_t **head 作為參數。
將函式名稱前加上指標變為 pointer to function returning type ，將使回傳類型為指標，而指標的副本仍指向同一個位置，因此可回傳修改後的原始 linked list 。

案例探討: LeetCode 21. Merge Two Sorted Lists

使用 indirect pointer

struct ListNode *mergeTwoLists(struct ListNode *L1, struct ListNode *L2) {
    struct ListNode *head = NULL, **ptr = &head, **node;

    for (node = NULL; L1 && L2; *node = (*node)->next) {
        node = (L1->val < L2->val) ? &L1: &L2;
        *ptr = *node;
        ptr = &(*ptr)->next;
    }
    *ptr = (struct ListNode *)((uintptr_t) L1 | (uintptr_t) L2);
    return head;
}

但如何取值做合併也是非常重要

naive

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (listsSize == 0) return NULL;
    for (int i = 1; i < listsSize; i++)
        lists[0] = mergeTwoLists(lists[0], lists[i]);
    return lists[0];
}

缺點 : 以不斷增長的第一條串列去添加剩餘的串列，造成合併速度減緩。

頭跟尾兩兩合併

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (listsSize == 0) return NULL;
    
    while (listsSize > 1) {
        for (int i = 0, j = listsSize - 1; i < j; i++, j--)
            lists[i] = mergeTwoLists(lists[i], lists[j]);
        listsSize = (listsSize + 1) / 2;
    }
    
    return lists[0];
}

多條串列頭尾兩兩合併，類似等差級數求和之梯形公式，多數情況下長度較平均，合併較快。

分段合併

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (listsSize == 0) return NULL;
    
    for (int interval = 1; interval < listsSize; interval *= 2) 
        for (int i = 0; i + interval < listsSize; i += interval * 2) {
            lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
        }
    
    return lists[0];
}

其方法類似 count leading zero
以下為 unsign_int 32 實作

uint16_t count_leading_zeros(uint32_t x)
{
    x |= (x >> 1);
    x |= (x >> 2);
    x |= (x >> 4);
    x |= (x >> 8);
    x |= (x >> 16);

    /* count ones (population count) */
    x -= ((x >> 1) & 0x55555555);
    x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
    x = ((x >> 4) + x) & 0x0f0f0f0f;
    x += (x >> 8);
    x += (x >> 16);

    return (32 - (x & 0x7f));
}

大致上概念為將最高位1右側bit全補為1，並以以下視覺化圖片實作計算右側 1 總數。

Divide and Conquer

struct ListNode *mergeKLists(struct ListNode **lists, int listsSize) {
    if (!listsSize)
        return NULL;
    if (listsSize <= 1)
        return *lists;

    int m = listsSize >> 1;
    struct ListNode *left = mergeKLists(lists, m);
    struct ListNode *right = mergeKLists(lists + m, listsSize - m);

    return mergeTwoLists(left, right);
}

不斷分左右邊直到 listSize <= 1，並會先做 mergeTwoLists 再回傳，因此最後也是經排序過之資料。

案例探討: Leetcode 2095. Delete the Middle Node of a Linked List

快慢指標

struct ListNode *deleteMiddle(struct ListNode *head) {
    if (!head->next) return NULL;
    
    struct ListNode **indir = &head, *prev = NULL;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
        prev = *indir;
        indir = &(*indir)->next;
    }
    prev->next = (*indir)->next;
    free(*indir);
    return head;
}

這裡考慮給定的鏈結串列為 [1, 3, 4, 7, 1, 2, 6]，上述的程式碼在迴圈結束後，*indir 會指向內容為 7 的節點 (以下記做 node7)，prev 緊隨其後指向內容為 4 的節點 (以下記做 node4)，換言之，prev->next 就是 *indir。

找出 indir 跟 prev 所指向的節點與關係後，可知 prev->next = (*indir)->next; 相當於 (*indir) = (*indir)->next;，而 **indir 為指標的指標，因此他會指向指向 prev->next 的 node ，即 prev ，因此 *indir 會從 node4 指向 node1。

在 free(*indir) 時， node1 會被 free 掉，而被偵測到 heap-use-after-free。
因此改用 *next 來儲存 (*indir)->next

struct ListNode *deleteMiddle(struct ListNode *head) {
    if (!head->next) return NULL;
    
    struct ListNode **indir = &head, *prev = NULL;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next) {
        prev = *indir;
        indir = &(*indir)->next;
    }
    struct ListNode *next = (*indir)->next;
    free(*indir);
    prev->next = next; // *indir = next
    return head;
}

或無須 prev 指標：

struct ListNode *deleteMiddle(struct ListNode *head) {
    struct ListNode **indir = &head;
    for (struct ListNode *fast = head; fast && fast->next; fast = fast->next->next)
        indir = &(*indir)->next;
    struct ListNode *del = *indir;
    *indir = (*indir)->next;
    free(del);
    return head;
}

須留意指標的指標的應用以避免指向錯誤之處。
快慢指標的應用，這邊我的第一想法會是第一次遍歷一次 linked list 並記錄數量，然後再一次遍歷，直到數到中間那一個。若以快慢指標， fast 一次動兩格，而 indir 一次動一格，那 fast 抵達終點時 indir 剛好位於中間，因此可以一次遍歷並無須花費額外記憶體儲存，

案例探討: LeetCode 86. Partition List

目的為：給定一個鏈結串列跟整數 x，將串列分割成兩組，比 x 小的節點置前，大於或等於 x 的節點置後，應維持分割前的順序。

struct ListNode *partition(struct ListNode *head, int x)
{
    struct ListNode *l2 = NULL;
    struct ListNode **p1 = &head, **p2 = &l2;
    
    for (struct ListNode *node = head; node; node = node->next) {
        if (node->val < x) {
            *p1 = node;
            p1 = &(*p1)->next;
        } else {
            *p2 = node;
            p2 = &(*p2)->next;
        }
    }
	
    *p1 = l2;
    *p2 = NULL;
    return head;
}

利用「指標的指標的指標」來簡化程式碼

struct ListNode *partition(struct ListNode *head, int x)
{
    struct ListNode *l2 = NULL;
    struct ListNode **p1 = &head, **p2 = &l2;
    
    for (struct ListNode *node = head; node; node = node->next) {
        struct ListNode ***indir = node->val < x ? (&p1): (&p2);
        **indir = node;
        *indir = &(**indir)->next;
    }
	
    *p1 = l2;
    *p2 = NULL;
    return head;
}

先利用 ***indir 來決定要接在哪一個指標的指標，才開始接。

circular linked list
Cycle detection

Let μ be the smallest index such that the value xμ reappears infinitely often within the sequence of values xi, and let λ (the loop length) be the smallest positive integer such that xμ = xλ + μ. The cycle detection problem is the task of finding λ and μ.

這邊不貼教材原始碼，只解釋教材裡面沒解釋到的變數。

Linux 核心原始程式碼

WRITE_ONCE

藉由 WRITE_ONCE 和 READ_ONCE 的使用，可以避免編譯器合併、切割、甚至重排特定的記憶體讀寫操作。下面是 WRITE_ONCE 的定義:
#define WRITE_ONCE(x, val)				\
({							\
	union { typeof(x) __val; char __c[1]; } __u =	\
		{ .__val = (val) }; 			\
	__write_once_size(&(x), __u.__c, sizeof(x));	\
	__u.__val;					\
})
我們可以再次看到 statement expression 技巧的應用。此外，可以看到 WRITE_ONCE 把 val 寫入 union 結構中，使其與一個 char __c[1] 共享空間。藉由以 union 為基礎的 type-punning 技巧，可避免違反 strict aliasing 規則，使得 __c 能作為這個 union 的指標來使用，從而允許編譯器最佳化。

何謂 aliasing

其所指為同一個位置可被多個 symbol 存取時，這種情形會造成編譯器最佳化的限制。根據 Options That Control Optimization， -fstrict-aliasing 參數會讓編譯器假設程式撰寫者不會將相似類型 (例如 int 和 unsigned int) 以外的指標予以指向同一塊記憶體空間，以允許做更激進的最佳化。

Linux 核心的 list_sort 實作

方法會保持兩個要被 merge 的 list 至少是 2 : 1 的狀態 (較大的 list 至多是較小者的 2 倍)，這可有效的降低比較的次數。list_sort 與一般的 fully-eager bottom-up mergesort 方法不同，後者只要出現兩個
$2^{k}$ 大小的 list，就會立刻被合併。而前者的方法是在出現兩個
$2^{k}$ 大小的 list 的時候，不立即合併，反之，一直等到下一個
$2^{k}$ 的 list 被蒐集起來時，前者的這兩個 linked list 才會被合併起來。只要這 2 : 1 的 list 可以完全被放到 cache 裡，就可避免 cache thrashing。

方法中會透過一個 count 來紀錄 pending 的節點數量。當目前的 count + 1 後，會設置第
$k$ 個 bit 為 1，
$k - 1$ 至 0 bit 為 0 時(除了 count 為
$2^{k} - 1$ 的情境)，我們就把兩個
$2^{k}$ 長度的 list 做合併。

$2^{0}$
$\to$ count = 1 =
$1_{2}$
$\to$
$2^{0}$ +
$2^{0}$ (no merge)

$2^{0}$ +
$2^{0}$
$\to$ count = 2 =
$10_{2}$
$\to$
$2^{1}$ +
$2^{0}$ (將
$10_{2}$ 加 1 的話 set bit 0，merge to 2^1)

$2^{1}$ +
$2^{0}$ count = 3 =
$11_{2}$ ->
$2^{1}$ +
$2^{0}$ +
$2^{0}$ (no merge)

$2^{1}$ +
$2^{0}$ +
$2^{0}$
$\to$ count = 4 =
$100_{2}$
$\to$
$2^{1}$ +
$2^{1}$ +
$2^{0}$ (將
$100_{2}$ 加 1 的話 set bit 0
$\to$ merge to
$2^{1}$ )

$2^{1}$ +
$2^{1}$ +
$2^{0}$
$\to$ count = 5 =
$101_{2}$
$\to$
$2^{2}$ +
$2^{0}$ +
$2^{0}$ (將
$101_{2}$ 加 1 的話 set bit 1
$\to$ merge to
$2^{2}$ )

$2^{2}$ +
$2^{0}$ +
$2^{0}$
$\to$ count = 6 =
$110_{2}$
$\to$
$2^{2}$ +
$2^{1}$ +
$2^{0}$ (將
$110_{2}$ 加 1 的話 set bit 0
$\to$ merge to
$2^{1}$ )

當 count == 5 再加 1 後，會設置第

k

個 bit 為 1 ，而這裡

k

= 1 ( 因從 兩個

2^{k}

大小的 list 這句話看出

k

指的是存在兩個相同大小 list 的指數，因此

k

便是 1 )，而

k - 1

至 0 bit 為 0 時，就把兩個

2^{k}

長度的 list 做合併。而範例給的是 count = 5 =

101_{2}

，再加 1 ，變為

110_{2}

，同時設置第 1 個 bit 為 1 ，因

k - 1

(0) 至 0 bit 為 0 ，因此合併。

2024q1 Homework1 (lab0)

1. 第 1 週所有教材及作業描述，啟發和疑惑

一、 解讀計算機編碼

二、 你所不知道的C語言：指標篇

三、 你所不知道的 C 語言: linked list 和非連續記憶體

四、Linux 核心設計: 作業系統術語及概念

Read more

Linux 核心專題: 回顧 bitops 並改進

2024q1 Homework2 (quiz1+2)

Performance Analysis of the IEEE 802.11 Distributed Coordination Function

FNS 改進

一、解讀計算機編碼

二、你所不知道的C語言：指標篇

三、你所不知道的 C 語言: linked list 和非連續記憶體