# 2023q1 Homework3 (quiz3)
contributed 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$ 分為以下兩種情況:
1. `x` 是 2 的冪 : $\lceil log_{2}(x) \rceil$ 為位元中 1 所在的最高位位置
2. `x` 不是 2 的冪: $\lceil log_{2}(x) \rceil$ 為位元中 1 所在的最高位位置加一
* 透過二分搜尋來找出 1 所在的最高位位置
* `x--` 確保 `x` 的位元中 1 所在的最高位位置小於 $\lceil log_{2}(x) \rceil$，因此不管 `x` 是否為 2 的冪，位元中 1 所在的最高位位置加一就是 $\lceil log_{2}(x) \rceil$
* 當 `x` 為 1 時輸出應為 0 ，不過這個實作會輸出 1 ，因為 `x--` 後位元中 1 所在的最高位位置應該不為 0 ， 下面的實作可以改善這個問題

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

    int ceil = !((x & x-1) == 0);
    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) + ceil;       
}

* `(x & x-1) == 0` 可以判斷 x 是否為 2 的冪，也就可以判別 $\lceil log_{2}(x) \rceil$ 的兩種情況， 因此找出 `x` 位元中 1 所在的最高位位置再加上 `!((x & x-1) == 0)` 就可以求得 $\lceil log_{2}(x) \rceil$

[題目連結](https://hackmd.io/@sysprog/linux2023-quiz3#%E6%B8%AC%E9%A9%97-3)