# 2022q2 Homework (quiz4)

contributed by <`ray90514`>

# 測驗1
求 log2 相當於求最高位的 1 在第幾位，以 `uint32_t` 為例，如果某數 `x` 最高位的 1 在高16位，則該數會大於 `0xFFFF` ，最高位的 1 會在 16 + n 位，這個 n 用二分搜尋法對 `x` 以同樣的方法求得。因為是求 ceil 所以結果要 +1 ，對於特殊情況也就是 2 的冪則是一開始先減一處理。
這段程式碼照邏輯少了以下

r |= shift;
shift = x > 0x1;
r |= shift

合併之後為 `r | shift | x >> 1` ，因為此時 `x` 的值只可能是 0 ~ 3 ， `x > 0x1` 可用 `x >> 1` 取代。

# 測驗2

程式的運作為二分搜尋，使用一個可以取得右半邊的值的 bitmask `t` ，如果 `x` 最低位的 1 在右半邊，則 `x & t` 非 0 ，反之，若該值為 0 ，則最低位的 1 會在 shift + n 。因此 `EXP2` 為 `x & t` ， `EXP3` 為 `o += shift` 。

## 改進

#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 = 0;
    size_t shift;

    shift = ((x & 0xFFFF) == 0) << 4;
    x >>= shift;
    o |= shift;
    shift = ((x & 0xFF) == 0) << 3;
    x >>= shift;
    o |= shift;
    shift = ((x & 0xF) == 0) << 2;
    x >>= shift;
    o |= shift;
    shift = ((x & 0x3) == 0) << 1;

    return (o | shift | !(x & 0x1)) + 1;
}

# 測驗3

`con` 是一個指向指標的指標，在走訪的過程中他會指向節點的 `next` 指標，所以 `EXP4` 為 `&(*con)->next`。當條件成立時，這個 `next` 指標指向要被移除節點，將該 `next` 指標指向要被移除節點的 `next` ，就可將該節點移除。因此 `EXP5` 為 `fc->next`

# 測驗4

# 測驗5

###### tags: `linux2022`