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\)

題目連結