---
# System prepended metadata

title: 2024q1 Homework2 (quiz1+2)

---

# 2024q1 Homework2 (quiz1+2)

contributed by < [`Wufangni`](https://github.com/Wufangni) >

## 第一週測驗題


### 測驗 1

#### list_tail
``` c
node_t *list_tail(node_t **left)
{
    while ((*left) && (*left)->next)
        left = &((*left)->next);
    return *left;
}
```
找出 list 最尾端的節點，```*left``` 指向 list 中的第一個節點依序往下走，直到 ```*left->next``` 遇到 NULL 為止。

```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=node1]
        n2[label=node2]
        
        
        NULL[label=NULL,shape=plaintext]
        n1 -> n2 ->NULL
        {
            rank="same";
            L[label="**left", shape=plaintext, fontcolor=blue]
            left[label="*left", shape=plaintext, fontcolor=blue]
            left -> n1[color=blue]
            L -> left[color=blue];
        }
        {
            rank="same";
            left_n[label="(*left)->next", shape=plaintext, fontcolor=blue]
            left_n -> n2[color=blue]
            ;
        }
        
}
```
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=node1]
        n2[label=node2]
        
        
        NULL[label=NULL,shape=plaintext]
        n1 -> n2 ->NULL
        {
            rank="same";
            L[label="**left", shape=plaintext, fontcolor=blue]
            left[label="*left", shape=plaintext, fontcolor=blue]
            left -> n2[color=blue]
            L -> left[color=blue];
        }
        {
            rank="same";
            left_n[label="(*left)->next", shape=plaintext, fontcolor=red]
            left_n -> NULL[color=red]
            ;
        }
        
}
```


#### list_length
``` c
int list_length(node_t **left)
{
    int n = 0;
    while (*left) {
        ++n;
        left = &((*left)->next);
    }
    return n;
}
```
與上述方法類似，因為計算總節點數須走完全部節點所以判斷條件到 ```*left``` 指到 NULL 為止。

#### quick_sort

``` c
void quick_sort(node_t **list)
{
    int n = list_length(list);
    int value;
    int i = 0;
    int max_level = 2 * n;
    node_t *begin[max_level], *end[max_level];
    node_t *result = NULL, *left = NULL, *right = NULL;
    
    begin[0] = *list;
    end[0] = list_tail(list);
            
    while (i >= 0) {
        node_t *L = begin[i], *R = end[i];
        if (L != R) {
            node_t *pivot = L;
            value = pivot->value;
            node_t *p = pivot->next;
            pivot->next = NULL;
    
            while (p) {
                node_t *n = p;
                p = p->next;
                list_add(n->value > value ? &right : &left, n);
            }

            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);

            left = right = NULL;
            i += 2;
        } else {
            if (L)
                list_add(&result, L);
            i--;
        }
    }
    *list = result;
}

```
begin[0] 和 end[0] 初始值設置為 list 的頭及尾端，分別以 L 及 R 兩個 ```*node_t``` 型態包裝，先將掃過 list 將小於 pivot 的節點以 list_add 方式加到 left 前端，若大於 pivot 則加到 right 前端。
- Step 1
begin[0] 及 end[0] 紀錄 left 頭及尾端節點， begin[1] 及 end[1] 紀錄當前 pivot 節點，begin[2] 及 end[2] 紀錄 right 頭及尾端節點。
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n11[label=7]
        n12[label=5]
        n10[label=4]
        n7[label=2]
        n8[label=3]
        n9[label=1]
        n1[label=4]
        n2[label=1]
        n3[label=3]
        n4[label=5]
        n5[label=2]
        n6[label=7]
        
        n1 -> n2 -> n3 -> n4 -> n5 -> n6
        n7 -> n8 -> n9
        n10
        n11 -> n12
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n1
            pivot -> n1[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n6
        }
        {
            rank="same";
            begin0[label="begin[0]", shape=plaintext]
            begin0 -> n7
        }
        {
            rank="same";
            end0[label="end[0]", shape=plaintext]
            end0 -> n9
        }
        
        {
            rank="same";
            end1[label="begin[1] \\ end[1]", shape=plaintext]
            end1 -> n10
        }
        {
            rank="same";
            begin2[label="begin[2]", shape=plaintext]
            begin2 -> n11
        }
        {
            rank="same";
            end2[label="end[2]", shape=plaintext]
            end2 -> n12
        }
}
```


- Step 2 重複上一步驟，pivot 變為 L 所在節點。
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n11[label=7]
        n10[label=5]
        n1[label=7]
        n2[label=5]
        
        
        n1 -> n2 
        n10
        n11
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n1
            pivot -> n1[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n2
        }
        {
            rank="same";
            end1[label="begin[2] \\ end[2]", shape=plaintext]
            end1 -> n10
        }
        {
            rank="same";
            begin2[label="begin[3] \\ end[3]", shape=plaintext]
            begin2 -> n11
        }
}
```


- Step 3
此時 begin[3] 及 end[3] 都指向同一節點，表示只有一個節點在 begin[3] 當中(後半部分已完成排序)，將 L 加入 result 前端再繼續往下判斷。
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n1[label=4]
        n2[label=5]
        n3[label=7]
        
        n1 -> n2 -> n3
        {
            rank="same"; 
            L[label="result", shape=plaintext]
            L -> n1
            
        }
        
}
```

- Step 4
begin[0] 及 end[0] 不相等，將 list 從頭到尾掃一次，比 pivot 小記錄到 begin[0]，反之則記錄到 begin[2]。
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        n12[label=3]
        n11[label=2]
        n10[label=1]
        n7[label=2]
        n8[label=3]
        n9[label=1]
        
        n7 -> n8 -> n9
        n10
        
        
        {
            rank="same";
            
            pivot[label="pivot", shape=plaintext, fontcolor=red]
            L[label="L", shape=plaintext]
            L -> n7
            pivot -> n7[color=red]
        }
        {
            rank="same";
            R[label="R", shape=plaintext]
            R -> n9
        }
        
        {
            rank="same";
            end0[label="begin[0] \\ end[0]", shape=plaintext]
            end0 -> n10
        }
        {
            rank="same";
            end1[label="begin[1] \\ end[1]", shape=plaintext]
            end1 -> n11
        }
        {
            rank="same";
            end2[label="begin[2] \\ end[2]", shape=plaintext]
            end2 -> n12
        }
}
```



- Step 5
因 begin[0]~begin[2] 都只有一個節點，依序將 L 加入 result。
```graphviz
digraph name{
        node[shape=box]        
        rankdir = LR
        
        n1[label=1]
        n2[label=2]
        n3[label=3]
        n4[label=4]
        n5[label=5]
        n6[label=7]
        
        n1 -> n2 -> n3 -> n4 -> n5 -> n6
        
        {
            rank="same";
            
            
            L[label="result", shape=plaintext]
            L -> n1
            
        }
        
}
```
#### `改進方法`
若遇到特殊情況(例如降冪排序或升冪排序)，每次故左邊第一個做 `pivot` 會導致 worse case 產生，即時間複雜度為 $O(n^2)$，在挑選 `pivot` 時參考 [`ChiTingCheng`](https://hackmd.io/@r36EKfH2TwalEWG_fUuSyg/linux2024-homework2) 同學的改進方案，每輪重新選擇 `pivot` 時以隨機取代固定挑選，更大程度避免陷入 worse case 。

``` c
node_t *pivot = pivot_select(L);
```

### 測驗 2
#### timesort

``` c
#include <stdint.h>
#include <stdlib.h>

#include "list.h"
#include "sort_impl.h"

static inline size_t run_size(struct list_head *head)
{
    if (!head)
        return 0;
    if (!head->next)
        return 1;
    return (size_t) (head->next->prev);
}

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

static size_t stk_size;

static struct list_head *merge(void *priv,
                               list_cmp_func_t cmp,
                               struct list_head *a,
                               struct list_head *b)
{
    struct list_head *head;
    struct list_head **tail = &head;

    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;
            }
        }
    }
    return head;
}

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;
}

static void merge_final(void *priv,
                        list_cmp_func_t cmp,
                        struct list_head *head,
                        struct list_head *a,
                        struct list_head *b)
{
    struct list_head *tail = head;

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

    /* Finish linking remainder of list b on to tail */
    build_prev_link(head, tail, b);
}

static struct pair find_run(void *priv,
                            struct list_head *list,
                            list_cmp_func_t cmp)
{
    size_t len = 1;
    struct list_head *next = list->next, *head = list;
    struct pair result;

    if (!next) {
        result.head = head, result.next = next;
        return result;
    }

    if (cmp(priv, list, next) > 0) {
        /* decending run, also reverse the list */
        struct list_head *prev = NULL;
        do {
            len++;
            list->next = prev;
            prev = list;
            list = next;
            next = list->next;
            head = list;
        } while (next && cmp(priv, list, next) > 0);
        list->next = prev;
    } else {
        do {
            len++;
            list = next;
            next = list->next;
        } while (next && cmp(priv, list, next) <= 0);
        list->next = NULL;
    }
    head->prev = NULL;
    head->next->prev = (struct list_head *) len;
    result.head = head, result.next = next;
    return result;
}

static struct list_head *merge_at(void *priv,
                                  list_cmp_func_t cmp,
                                  struct list_head *at)
{
    size_t len = run_size(at) + run_size(at->prev);
    struct list_head *prev = at->prev->prev;
    struct list_head *list = merge(priv, cmp, at->prev, at);
    list->prev = prev;
    list->next->prev = (struct list_head *) len;
    --stk_size;
    return list;
}

static struct list_head *merge_force_collapse(void *priv,
                                              list_cmp_func_t cmp,
                                              struct list_head *tp)
{
    while (stk_size >= 3) {
        if (run_size(tp->prev->prev) < run_size(tp)) {
            tp->prev = merge_at(priv, cmp, tp->prev);
        } else {
            tp = merge_at(priv, cmp, tp);
        }
    }
    return tp;
}

static struct list_head *merge_collapse(void *priv,
                                        list_cmp_func_t cmp,
                                        struct list_head *tp)
{
    int n;
    while ((n = stk_size) >= 2) {
        if ((n >= 3 &&
             run_size(tp->prev->prev) <= run_size(tp->prev) + run_size(tp)) ||
            (n >= 4 && run_size(tp->prev->prev->prev) <=
                           run_size(tp->prev->prev) + run_size(tp->prev))) {
            if (run_size(tp->prev->prev) < run_size(tp)) {
                tp->prev = merge_at(priv, cmp, tp->prev);
            } else {
                tp = merge_at(priv, cmp, tp);
            }
        } else if (run_size(tp->prev) <= run_size(tp)) {
            tp = merge_at(priv, cmp, tp);
        } else {
            break;
        }
    }

    return tp;
}

void timsort(void *priv, struct list_head *head, list_cmp_func_t cmp)
{
    stk_size = 0;

    struct list_head *list = head->next, *tp = NULL;
    if (head == head->prev)
        return;

    /* Convert to a null-terminated singly-linked list. */
    head->prev->next = NULL;

    do {
        /* Find next run */
        struct pair result = find_run(priv, list, cmp);
        result.head->prev = tp;
        tp = result.head;
        list = result.next;
        stk_size++;
        tp = merge_collapse(priv, cmp, tp);
    } while (list);

    /* End of input; merge together all the runs. */
    tp = merge_force_collapse(priv, cmp, tp);

    /* The final merge; rebuild prev links */
    struct list_head *stk0 = tp, *stk1 = stk0->prev;
    while (stk1 && stk1->prev)
        stk0 = stk0->prev, stk1 = stk1->prev;
    if (stk_size <= FFFF) {
        build_prev_link(head, head, stk0);
        return;
    }
    merge_final(priv, cmp, head, stk1, stk0);
}
```

## 第二週測驗題
### 測驗 1
#### hlist_add_head

``` c
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
{
    if (h->first)
        h->first->pprev = &n->next;
    n->next = h->first;
    n->pprev = &h->first;
    h->first = n;
}
```
- Step1: 如果 ```h->first``` 存在，則將此節點的 ```pprev``` 指向 ```&n->next```


<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/rJfzk-9T6.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step2: 新增 n 節點的 ```*next``` 指向 ```h->first```
<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/BJuq1b9aa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step3: n 節點的 ```*pprev``` 指向 ```&h->first```
<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/B1MMxZ5pa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

- Step4: ```h->first``` 指向 n 節點
<div style="text-align: center;">
    <img src="https://hackmd.io/_uploads/HkhOgZ5aa.png" alt="Image Alt Text" style="width: 70%; height: auto;margin: 10px;">
</div>

#### find
計算 ```hash``` 值後用 ```hlist_for_each``` 從對應雜湊值 ```&heads[hash]``` 開始往下找尋，使用 ```container_of``` 找出此節點的實體位置跟 ```num``` 進行比對，若相同則回傳該節點的 ```inx``` 。
``` c
static int find(int num, int size, const struct hlist_head *heads)
{
    struct hlist_node *p;
    int hash = (num < 0 ? -num : num) % size;
    hlist_for_each (p, &heads[hash]) {
        struct order_node *on = container_of(p, struct order_node, node);
        if (num == on->val)
            return on->idx;
    }
    return -1;
}
```
#### node_add
使用 ```malloc``` 分配空間給 ```*on``` ，填入對應的 ```val``` 及 ```idx``` 並計算 ```hash``` 值，將其加入 ```&heads[hash]``` 位置。
``` c
static inline void node_add(int val,
                            int idx,
                            int size,
                            struct hlist_head *heads)
{
    struct order_node *on = malloc(sizeof(*on));
    on->val = val;
    on->idx = idx;
    int hash = (val < 0 ? -val : val) % size;
    hlist_add_head(&on->node, &heads[hash]);
}
```
#### dfs
利用中序數列創建一個以中序排列的鏈結串列 ```*in_heads``` 。
```c
struct hlist_head *in_heads = malloc(inorderSize * sizeof(*in_heads));
for (int i = 0; i < inorderSize; i++)
    INIT_HLIST_HEAD(&in_heads[i]);
for (int i = 0; i < inorderSize; i++)
    node_add(inorder[i], i, inorderSize, in_heads);
```
用 ```find``` 找到在中序裡的 ```idx``` ，使用 ```pre_low``` \ ```pre_high``` \ ```in_low``` \ ```in_high``` 分別對左子樹及右子樹做遞迴。
``` c
static struct TreeNode *dfs(int *preorder,
                            int pre_low,
                            int pre_high,
                            int *inorder,
                            int in_low,
                            int in_high,
                            struct hlist_head *in_heads,
                            int size)
{
    if (in_low > in_high || pre_low > pre_high)
        return NULL;

    struct TreeNode *tn = malloc(sizeof(*tn));
    tn->val = preorder[pre_low];
    int idx = find(preorder[pre_low], size, in_heads);
    tn->left = dfs(preorder, pre_low + 1, pre_low + (idx - in_low), inorder,
                   in_low, idx - 1, in_heads, size);
    tn->right = dfs(preorder, pre_high - (in_high - idx - 1), pre_high, inorder,
                    idx + 1, in_high, in_heads, size);
    return tn;
}
```
- 左子樹
1. ```pre_low``` : 為原本自己再加一，根據前序性質為根節點的下一節點。
2. ```pre_high``` : 使用 ```idx - in_low``` 計算出根節點左子樹節點數，從 ```pre_low``` 往後加即為前序最高索引點。
3. ```in_low``` : 原先最低索引位置。
4. ```in_high``` : 根節點左邊位置。

- 右子樹
1. ```pre_low``` : ```in_high - idx``` 算出根結點右子樹節點數，再以原最高索引點 ```pre_high``` 減掉右邊總數再加回一，代表前序最低索引點位置。
2. ```pre_high``` : 原前序最高索引點。
3. ```in_low``` : 根節點右邊位置。
4. ```in_high``` : 原中序最高索引位置。

### 測驗 2
#### Least Recently Used (LRU) 
實作出 LRU 策略的雜湊儲存，先介紹 ```LRUCache``` 和 ```LRUNode``` 兩種結構。
``` c
struct hlist_head {
    struct hlist_node *first;
};
struct hlist_node {
    struct hlist_node *next, **pprev;
};
typedef struct {
    int capacity;
    int count;
    struct list_head dhead;
    struct hlist_head hhead[];
} LRUCache;

typedef struct {
    int key;
    int value;
    struct hlist_node node;
    struct list_head link;
} LRUNode;
```
```LRUCache``` 中使用了 ```list_head``` 結構的 ```dhead``` 用來串接最近一次存取的節點， ```hhead[]``` 則用來串接雜湊的 ```LRUNode``` 。
```graphviz
digraph {
    rankdir=LR;
    subgraph cluster_1{  
        node [shape=record];
        label = "LRUCache"
        list_head [label = "<h> dhead|{<next> next|<prev> prev}", group = list];
        other[label = "<cap> capacity"]
        other2[label = "<count> count"]
        hlist_head [label = "<h> hhead[]|...|... |...  "];
    }  
}
```
```graphviz
digraph {
    rankdir=LR;
    subgraph cluster_1{  
        node [shape=record];
        label = "LRUNode"
        
        other[label = "<cap> key"]
        other2[label = "<count> value"]
        list_head [label = "<h> link|{<prev> prev | <next> next}", group = list];
        hlist_head [label = "<h> node|{<prev> pprev | <next> next}"];
    }  
}
```


#### lRUCacheCreate
使用 ```malloc``` 分配空間給 ```*cache``` ，將兩型態為 ```int``` 的變數初始值定義完後使用 ```INIT_LIST_HEAD``` 初始化 ```dhead``` 及 ```hhead[]``` 。
``` c
LRUCache *lRUCacheCreate(int capacity)
{
    LRUCache *cache = malloc(2 * sizeof(int) + sizeof(struct list_head) +
                             capacity * sizeof(struct hlist_head));
    cache->capacity = capacity;
    cache->count = 0;
    INIT_LIST_HEAD(&cache->dhead);
    for (int i = 0; i < capacity; i++)
        INIT_HLIST_HEAD(&cache->hhead[i]);
    return cache;
}
```
#### lRUCacheFree
使用 ```list_for_each_safe``` 逐一釋放 ```dhead``` 串聯的 ```LRUNode``` ， 最後釋放整個 ```LRUCache``` 。
``` c
void lRUCacheFree(LRUCache *obj)
{
    struct list_head *pos, *n;
    list_for_each_safe (pos, n, &obj->dhead) {
        LRUNode *cache = list_entry(pos, LRUNode, link);
        list_del(&cache->link);
        free(cache);
    }
    free(obj);
}
```
#### lRUCacheGet
利用 ```key``` 的值除以總容量取餘數算出雜湊值 ```hash``` ，從 ```&obj->hhead[hash]``` 開始找若此 ```LRUNode``` 的值與 ```key``` 相符，則從 ```dhead``` 中移除，並回傳此 ```LRUNode``` 的 ```value``` 。
``` c
int lRUCacheGet(LRUCache *obj, int key)
{
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *cache = list_entry(pos, LRUNode, node);
        if (cache->key == key) {
            list_move(&cache->link, &obj->dhead);
            return cache->value;
        }
    }
    return -1;
}
```

#### lRUCachePut
先計算出雜湊值 ```hash``` ，從 ```&obj->hhead[hash]``` 逐一找尋若有相同資料已存在在 ```*obj``` 中則從 ```&obj->dhead``` 中移除，無相同值需判斷目前容量是否已滿。
容量已滿的情況，將 ```dhead``` 最前端紀錄的 ```LRUNode``` (表示最久未被存取的資料)移除，並將新節點加入 ```&obj->hhead[hash]``` 位置。
尚有容量則直接分配記憶體空間給新增節點，將其加入 ```&obj->hhead[hash]``` 位置並更新 ```&obj->dhead``` 。
``` c
void lRUCachePut(LRUCache *obj, int key, int value)
{
    LRUNode *cache = NULL;
    int hash = key % obj->capacity;
    struct hlist_node *pos;
    hlist_for_each (pos, &obj->hhead[hash]) {
        LRUNode *c = list_entry(pos, LRUNode, node);
        if (c->key == key) {
            list_move(&c->link, &obj->dhead);
            cache = c;
        }
    }

    if (!cache) {
        if (obj->count == obj->capacity) {
            cache = list_last_entry(&obj->dhead, LRUNode, link);
            list_move(&cache->link, &obj->dhead);
            hlist_del(&cache->node);
            hlist_add_head(&cache->node, &obj->hhead[hash]);
        } else {
            cache = malloc(sizeof(LRUNode));
            hlist_add_head(&cache->node, &obj->hhead[hash]);
            list_add(&cache->link, &obj->dhead);
            obj->count++;
        }
        cache->key = key;
    }
    cache->value = value;
}
```

### 測驗3
#### __ffs
先以 ```#if BITS_PER_LONG == 64``` 判斷是否有 64 位元，可一次與 ```0xffffffff``` 做 ```&``` 判斷是否吋在 ```set bit``` ，接著由高往低判斷一次word可前進多少，最後回傳第一個遇到的 ```set bit``` 位置。
```c
#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;
}
```

#### __clear_bit
使用 ```BIT_MASK``` 建立只有第 nr 的 bit 為 1 的 ```mask``` ，對 ```*p``` 與 ```~mask``` 做 ```&``` 得到只有第 nr 個 bit 被清空的狀態。
``` c
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;
}
```

#### FIND_NTH_BIT

``` c
#define FIND_NTH_BIT(FETCH, size, num)                          \
    ({                                                          \
        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;                                            \
        }                                                       \
                                                                \
        if (sz < BITS_PER_LONG)                              \
            tmp = (FETCH) & BITMAP_LAST_WORD_MASK(sz);          \
    found:                                                      \
        sz = min(idx * BITS_PER_LONG + fns(tmp, nr), sz);       \
    out:                                                        \
        sz;                                                     \
    })
```