# 2022q1 Homework4 (quiz4)
contributed by < `happyjack91630` >
> [作業需求](https://hackmd.io/@sysprog/linux2022-homework4)

:::danger
注意書寫規範和使用通順的漢語。
:notes: jserv
:::

## 測驗 `1` : $\lceil log_2(x) \rceil$
:::success
EXP1 = r | shift | x >> 1
:::
延伸第 3 週測驗題的測驗 `7`，已知輸入必為大於 `0` 的數值 (即 `x > 0`)，以下程式碼可計算 ⌈log2(x)⌉ ，也就是 ceil 和 log2 的組合並轉型為整數:

int ceil_log2(uint32_t x)
{
    uint32_t r, shift;

    x--;
    r = (x > 0xFFFF) << 4;   //0xFFFF = 0x0000FFFF                                                         
    x >>= r;
    shift = (x > 0xFF) << 3;
    x >>= shift;
    r |= shift;
    shift = (x > 0xF) << 2;
    x >>= shift;
    r |= shift;
    shift = (x > 0x3) << 1;
    x >>= shift;
    // r|= shift
    //shift = (x > 0x1) << 0;
    //r |= shift;
    return (EXP1) + 1;       
}

:::danger
power of 2 的翻譯是「2 的羃」，而非「羃次」
:notes: jserv
:::

這題其實想法跟第三周測驗題的測驗7的做法是類似的，利用**binary search**，找指定資料寬度中，二進位表示中最高位的 `1` 位元數所在處，但是這題要取`ceil`，所以要先減`1`(避免`x = 2 的冪`)，最後再將結果加1回來。觀察程式碼到最後只在比較停在第14行的`(x > 0x3)`，但是最後應該還要再比較`(x > 0x1)`是否還有shift，進而更新`r`。

//簡化部分 => EXP1
r |= shift
shift = (x > 0x1) << 0;
r |= shift;
//在簡化
r = r | shift | (x > 1)
//在簡化(因為x要比較最後2個bit(可能情況為0b00,0b11,0b10,0b01))
r = r | shift | x >> 1    


## 測驗 `2` ： find first set
:::success
EXP2 = x & t
EXP3 = o += shift
:::
複習〈你所不知道的 C 語言: bitwise 操作〉，改寫第 3 週測驗題的測驗 11 裡頭的 fls 函式 (fls 意謂 “find last set”)，使其得以計算 Find first set:

#define BITS_PER_BYTE 8
#define BITS_PER_LONG (sizeof(unsigned long) * BITS_PER_BYTE)

#include <stddef.h>

static inline size_t ffs(unsigned long x)
{
    if (x == 0)
        return 0;

    size_t o = 1; //這裡最低位元為1
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

    shift >>= 1;
    t >>= shift;

    while (shift) {
        if ((EXP2) == 0) {
            x >>= shift;
            EXP3;
        }

        shift >>= 1;
        t >>= shift;
    }
    return o;
}

`ffs`這個函式要查找第一個位置是1的bit位，但是是從bit 0(**最低位元**)開始找。想法也是跟**binary search**一樣。每次對半檢查`x`得下半部分是否有1。例如: x 的 `ffs` 在第17個bit，第一次就會檢查 0 ~ 15個bit是否有值，如果沒有(進if)就代表 `x` 的`ffs`一定落在16~31部分，所以就將x >> 16，且 o += 16，繼續對0~15對半找。反之 x 的ffs一定落在0 ~ 15部分，所以只需將`t`做調整，繼續對0~15對半找。

## 測驗 `3` ︰ pointer of a pointer
:::success
EXP4 = &(*con) -> next
EXP5 = fc -> next
:::
考慮以下改寫自 Linux 核心的程式碼:

struct foo_consumer {
    int (*handler)(struct foo_consumer *self, void *);
    struct foo_consumer *next;
};

struct foo {
    struct foo_consumer *consumers;
    unsigned long flags;
};

#include <stdbool.h>

/*
 * For foo @foo, delete the consumer @fc.
 * Return true if the @fc is deleted sfccessfully
 * or return false.
 */
static bool consumer_del(struct foo *foo, struct foo_consumer *fc)
{
    struct foo_consumer **con;
    bool ret = false;

    for (con = &foo->consumers; *con; EXP4) {
        if (*con == fc) {
            *con = EXP5;
            ret = true;
            break;
        }
    }

    return ret;
}

根據註解描述，這個程式碼是要刪除(但是這個程式碼又沒有將fc的空間free掉，所以叫remove會不會比較好呢??)`fc`這個node。這題就是要考**pointer of a pointer**，跟在linked list裡刪除node的作法是一模一樣的。可參考[你所不知道的 C 語言: linked list 和非連續記憶體](https://hackmd.io/@sysprog/c-linked-list)。
所以EXP4，走訪整個鏈結串列，所以就是`&(*con) -> next`，就能將con向前進了。EXP5則是在if找到要刪除的fc後，所執行的，所以將`*con`指向fc的下一個(`fc -> next`)就行了。