# 2022q1 Homework4 (quiz4)
contribute by < `Korin777` >

## 測驗一

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

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

* 此函式要求 $\lceil log_{2}(x) \rceil$
* 先將 `x--` ， 避免最後向上取整時 ， 當 $\lceil log_{2}(x) \rceil$ = $\lfloor log_{2}(x) \rfloor$ ， 我們算出來的 $\lceil log_{2}(x) \rceil$ 會多 1
* 2 進位表示中最高位為 1 之 bit 的位置(此位置從 0 開始)就是 $\lfloor log_{2}(x) \rfloor$) ， 函式的第 6 行到第 15 行還有 EXP1 就是在求它
eg : 對照$39_{10} = 00100111_{2}$
`x--` => $00100110_{2}$
0010 | 0110 => `x > 0xf , x >> 4 , r = 0 + 4 = 4` => 0010
00 | 10 => `x <= 0x3` => 10
10 => `r + x >> 1 = 4 + 1 = 5`
向上取整 `5 + 1 = 6`
## 測驗二

#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;
    unsigned long t = ~0UL;
    size_t shift = BITS_PER_LONG;

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

    while (shift) {
        if ((x & t) == 0) {
            x >>= shift;
            o += shift;
        }

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

    return o;
}

* Find first set: 找出最低位且為 1 的 bit 位置 ， 此位置從 1 開始
* 題目透過二分搜來找出最低位的 1 的位置 ， 將 x 尚未檢查過的 bit 分為左右兩半 ， 並檢查右半邊是否有 bit 為 1 來判斷 first set 在左半邊還右半邊 ， 如果在左半邊的話 `o` 會加上 `shift`(即 first set 所在位置至少會大於右半邊檢查過的 bit) ， 重複此動作直到 尚未檢查的 bit 只剩一個
e.g : 對照 $74_{10}=01001010_{2}$
0100 | 1010 => first set 在右半邊 ， 檢查右半邊 => 1010
10 | 10 => first set 在右半邊 ， 檢查右半邊 => 10
1 | 0 => first set 在左半邊 ， 檢查左半邊 ， `o = 1 + 1 = 2` => 1 ， 尚未檢查的 bit 只剩一個 ， 函式結束

[第 4 週測驗題](https://hackmd.io/@sysprog/linux2022-quiz4)