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

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

jserv

當 x 為 2ⁿ ，第 5 行 x-- 將 x 變成 0b111..111，避免在最後加一取 ceiling 時，計算錯誤為 2ⁿ⁺¹。

依序使用 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 。