---
tags: linux2023
---

# 2023q1 Homework3 (quiz3)
contributed by < `linhoward0522` >
>[2023q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz3)
## 測驗 `1`
## 測驗 `2`
## 測驗 `3`
---
## 測驗 `4`
已知輸入必為大於 `0` 的數值 (即 `x > 0`)，以下程式碼可計算 $⌈log_2(x)⌉$

- 先將 `x` 減去 `1`，這樣如果 `x` 是 `2` 的冪，就會變成比它小 `1` 的冪，這樣可以保證算出來的對數是正確的
- 使用 `r` 來保存對數的結果，如果 `x` 大於 `0xFFFF`，表示最高位為 `1` 的位置在較高的 `16` 位元，那麼 `r` 的值就設為 `16`，這樣可以將 `x` 右移 `16` 位，減少需要檢查的位數
- 若 `x` 小於 `0xFFFF`，則 `r` 的值就設為 `0`
- 接著以此類推，最後應要將 `r | shift` 更新上一步的結果，此時 `x` 剩下四種情況
- `0b11`
- `0b10`
- `0b01`
- `0b00`
- 因為還剩下兩個位元，所以需要使用 `x >> 1` 來判斷是否有高位元的 `1`，有的話就做 `|` 更新
- 最後要加上 `1` ，以取得 $⌈log_2(x)⌉$

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