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

$⌈ l o g_{2} (x) ⌉$ 分為以下兩種情況:
1. x 是 2 的冪 :
  $⌈ l o g_{2} (x) ⌉$ 為位元中 1 所在的最高位位置
2. x 不是 2 的冪:
  $⌈ l o g_{2} (x) ⌉$ 為位元中 1 所在的最高位位置加一
透過二分搜尋來找出 1 所在的最高位位置
x-- 確保 x 的位元中 1 所在的最高位位置小於
$⌈ l o g_{2} (x) ⌉$ ，因此不管 x 是否為 2 的冪，位元中 1 所在的最高位位置加一就是
$⌈ l o g_{2} (x) ⌉$
當 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 的冪，也就可以判別
$⌈ l o g_{2} (x) ⌉$ 的兩種情況，因此找出 x 位元中 1 所在的最高位位置再加上 !((x & x-1) == 0) 就可以求得
$⌈ l o g_{2} (x) ⌉$