# 2023q1 Homework3 (quiz3)
contributed by < `YSRossi` >

## 測驗 `4`

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

:::warning
逐行解讀程式碼之前，應先探討程式碼的作用和策略。
:notes: jserv
:::

當 `x` 為 2^n^ ，第 5 行 `x--` 將 `x` 變成 `0b111..111`，避免在最後加一取 ceiling 時，計算錯誤為 2^n+1^。

依序使用 `0xFFFF`, `0xFF`, `0xF`, `0x3` 每次將位元分成一半與 `x` 比較 ，使用 binary search 尋找值為 `1` 的最高位元在哪。`r` 紀錄 2 的冪，`shift` 會在過程中紀錄 `x` 要位移多少，每次位移的位數會加到 `r` 中，即 `r |= shift`。
第 16 行 shift 還沒加到 r 中，所以如同前面的操作，前半部分為 `r | shift` ，最後 `x` 還有 2 bits 未處理，因此補完後半部分的結果為 `r | shift | x >> 1`，即 2 bits 中的高位為 1 時，會額外加 1 。