# Week1

---

## 解讀計算機編碼

:::danger
第一次寫筆記，中文字跟英文都連在一起，好醜
:::

在二進位制下
* ones' complement:
假設A為4bit
`A + its ones' complement = 1111`
用 ones' 因為代表一連串的1

* two's complement:
(radix comlement)
假設 A 為 Nbit
`A + its two's complement =` $2^N$
two 代表 radix 為 2

若今天以十進位做運算，就稱為 10's complement
這個 2 or 10，代表的意思是 ==單一個 digit 所能擁有的狀態==，也就是==基數==(radix)

同樣的邏輯
radix 為 10 的時候，會有 nines' complement
radix 為 9 的時候，會有 eights' complement
...

Q : 那麼在二補數系統下，只有 1-bit 時能夠表示的範圍是?
A : 1-bit 的數值只有 0 跟 1，再來各自代表的意義究竟是實數的 (0,1) 還是 (0,-1) 就交給編譯器實作

參考 : [補數](https://zh.wikipedia.org/zh-tw/%E8%A1%A5%E6%95%B0)

N-bit的加法可以形成一個有限的阿貝爾群，再加上捨棄溢位即形成環
由於群的對稱性可以在環上畫出一條對稱軸。
對環以ones' complement解讀時，也能畫出一條較為傾斜的對稱軸。
為何two's complement會是ones' complement + 1?
因為two's complement的定義符合阿貝爾群的性質，對稱軸即為正中間那條，
可以發現兩種方法的對稱軸有段差距，當`0000`以阿貝爾群對稱軸找相反數，可以找到自己本身，當`0000`以ones' complement對稱軸找相反數，可以找到`1111`，和其本身差了`0001`。
所以做two's complement時，才會等於先做ones' complement再加上1。

N-bit數值編碼做加法
以3-bit為例
都是從000開始，順時鐘取圓弧
e.g. (-3) + (-1) = -4
101 + 111 = (1)100
畫圖可以知道，兩段圓弧拼接會繞一圈，最後終點在100
這樣就能解釋發生溢位的意義

---

## linked list和非連續記憶體操作

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;
    /**
     * list->head是一個指向Node的指標，儲存的是一個Node的address
     * &list->head取出這個指標本身的address 
    **/
    
    // 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;
    /**
     * (*indirect)->next是一個指向Node的指標，儲存的是一個Node的address.
     * 由此可知，xxx->head跟xxx->next是一樣的概念，都是指向一個Node.
     * indirect得到的是一個指標的address，該指標指向一個Node.
     * (*indirect)得到的是一個Node的address.
     * 當(*indirect) == target，代表indirect現在指向
     * 一個指標，該指標指向target，所以(*indirect)才會
     * 等於target.
    **/
    
}

linked list的操作可以不用考慮到node中存的是什麼type，從這裡可以延伸出一個概念，就是ADT(Abstract Data Type)，我的這個資料型態的操作可以用一個數學模型去描述，在C++ or Java中就有了iterator這個東西，達到資料封裝。

linked list中資料的交換，必須要維持常數時間，有效的交換才能拿來實作出排序，這會作用在file system中。因為file system的worst case、execution time需要被保證

Linux kernel提供的list.h(non thread-safe)，Glib提供的GList(thread-safe)，都可以無視內部的資料存了什麼東西，不用管多大多小，都能實作sort.

在多執行緒下的問題:
即使是thread-safe的linked list，也會有lock跟lock-free的差別
lock太多造成原本多執行緒應該期望效能得到提升，結果卻毫無改變甚至更糟。
linked list的delete、insert可能同時發生，產生一個根本不是linked list的東西，解決方法去看論文。

### 題目一

#### q1
* `FuncA`:新增一個Node在circular doubly-linked list的Tail
若list為empty(start point to NULL)則以此value建立新的list，該list僅有一個自己雙向循環的Node.
* `FuncB`:新增一個Node在circular doubly-linked list的Head(list為empty會出錯?)
* `FuncC`:在list中找到一個Node為Value2，並在他之後新增一個Node為Value1.(找不到會完蛋? 一直在While-loop)
* `display`:正向traversal跟反向traversal(list為empty會出錯?)

#### q2
* `FuncX`:原本應該是在作記錄，記錄list中有幾個node，不過因為FuncX內是`data++`而不是`(*data)++`，所以只是在記憶體位置上移動，main裡面的count都沒被改動到。如果list是循環的，最後node會是回到head，如果list不是循環的，最後node會是NULL，因此return value會兩種結果，0代表循環(head - head)，non-0代表非循環(NULL - head)。
* `node_new`:return type為struct node*，意即回傳一個pointer，其指向一個struct node。這個function作用是產生一個Node，其Next指標指向NULL。
* `main`:
* 第一次printf:前面先串起一個list為0-1-2-3-4-NULL，head指在0，非循環所以回傳是non-0，判斷為True，印出Yes.
* 第二次printf:list改串成0-1-2-3-0、4-NULL，head指在0，循環所以回傳是0，判斷為False，印出No.
* 第三次printf:可化簡為head->next = head->next，所以list沒變，跟上次printf一樣印出No.
* 第四次printf:可化簡為head->next = head，list改串成0-0、1-2-3-0、4-NULL，自己循環，所以回傳0，判斷為False，印出No.
* 第五次printf:因為count實際的值沒有被更動到，依然為0，印出0.

### 題目二

#### q3
* merge:指在此次sort新建立的已排序list的tail
* start:指在此次sort新建立的已排序list的head
* 此排序法的運作原理:
* 一般merge sort是切中間，這個排序法是把切在list的head，形成左右兩邊，兩邊再各自做此排序法，然而左邊只有一個node，所以只會得到該node的address，只有右邊會實際做sort。因此會先往右一直切，切到剩最後一個node與NULL做合併排序，return之後與一個原先在左邊的node做合併，不斷重複直到原先的head也做完合併.
* left跟right各自指著各自的已排序list.
* 第一輪會先挑出兩邊較小的node，由start+merge指著，意思是以該node建立一個新的已排序list，然後被挑選的那邊會指向自身list的下一個node.
* 接著每一輪for loop會挑出兩邊較小的一個node，接到merge的next，然後被挑選的那邊會指向自身list的下一個node.
* 直到left跟right都指到NULL，代表兩邊的node全都已經加入已排序好的list.
* return 已排序完成list的start位置

###### tags: `sysprog2020`