2023q1 Homework3 (quiz3)

contributed by < linhoward0522 >

2023q1 第 3 週測驗題

測驗 1

測驗 2

測驗 3

---

測驗 4

已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算

$\lceil lo{g}_2(x)\rceil$

• 先將 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 ，以取得
  $\lceil lo{g}_2(x)\rceil$

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