# 2019-06-03 張景雲

:::warning
:notes: 待做事項
1. 完整回覆題目並解釋
2. 列出實驗過程和參考資料
:::

## Q1: 實作將給定的==地址==做 align to 4-bytes 的 macro
Hint: Linux 核心有類似的程式碼
=>

#include <stdint.h>
#define ALIGN_TO_4BTYTE(x) (((uint_32t)(x)) + 0x03) & ~0x03

假設有一個數字他必須要是對齊4-byte，代表說這個數值必須要可以被4整除，那什麼情況下可以被4整除？ 要在`x & 0x03 == 0` 才會正確。因此我若想要做一個4-byte的對齊器，我就必須要在最後使用 bitmask(`11...11111100 == ~0x03`) 把最後兩位給消除掉。

在這邊 `(uint_32t)(x)) + 0x03` 的意義是要強迫進位到 > 4的位數

有一種例外情況，當 `x > 0xfffe` `x + 0x03` 會 overflow 導致結果不正確

### 推廣
假設我要做 n-btye 的對齊器 `n = 1 2 4 8 16 ...`

#include <stdint.h>
#define ALIGN_TO_NBTYTE(x,n) (((uint_32t)(x)) + (n-1)) & ~(n-1)

參考自 : [jserv note](https://hackmd.io/s/SyrZMGYr4)

---

## Q2: 假設一個 circular buffer 的容量為 `n = 1024`，用 bitwise 改寫原本 `x = (x + 1) % n` 的操作，使其達到更好的效能
Hint: 1024 is power of 2
=>
因為對於 2 的倍數 mod 其實只要對它做 (2^n-1) 即可達到一模一樣的效果。

x = (x+1) & (1024 - 1)

---

## Q3: Linux 的 linked list 對於 insertion/deletion 為何可做到 branchless?
因為在linux中，他是環狀的linked list，插頭不用說，已經有 head 資訊了，因此如果我想要差尾，其實我都頂多只需要往前走一格就是尾巴了。

 head->next->prev = new;
 new->next = head->next;
 new->prev = head;
 head->next = new;

## Q4: 以 Linux 的 linked list，實作「找到第 k 大的節點」
減少記憶體的操作數量
=>
最一開始給的solution

struct Mylist{
    int val;
    list_head* head;
}
...
// [5,7,1,3,4]
int top_k(struct Mylist* mylist,int k){
    if(!mylist) return NULL;
    int queue[k];
    int index = 0;
    struct Mylist* pos;
    list_for_each_entry(pos,mylist->head,head){
        int temp = pos->val;
        if(index < k){
            queue[index] = temp;
            index++;
        }
        else{
            for(int i=0;i<k;i++){
                if(temp >= queue[i]){
                    queue[i] = temp;
                    break;
                }
            }    
        }    
    }
    if(index < k-1) return NULL;
    int topk = INT_MAX;
    for(int i=0;i<k;i++){
        if(queue[i] <= topk) topk = queue[i];
    }
    return topk;
}

> 會有問題，因為 `queue[k]` 這東西很危險，你根本不知道 k 能夠多大，假設大到一個程度，程式就會 stack overflow，在加上這樣的資料結構設計，沒辦法重複利用，每次都要重算。可以利用 linked list 特性修正成更好的版本。