2024q1 Homework4 (quiz3+4)

contributed by < hugo0406 >

第三周測驗題

測驗一

測驗二

測驗三

版本一

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

版本一透過右移的操作來得到

$\lfloor lg(i)\rfloor$ ，每當右移一個位元，就對 log 加一，直到找到最高位元。然而當 i 的數值越大，迴圈進行的次數也會越多。

版本二

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= AAAA) {   //AAAA = 65536
        result += 16;
        i >>= 16;
    }
    while (i >= BBBB) {   //BBBB = 256
        result += 8;
        i >>= 8;
    }
    while (i >= CCCC) {   //CCCC = 16
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

版本二是將版本一進行改善，透過判斷條件一次右移多個位元來減少迴圈次數。

版本三

$\lfloor lg(i)\rfloor$ 的值取決於 i 的 msb 的位置 ，舉 i = 79 為例 ， i 的 msb 的位置為 6 ，

$\lfloor lg(i)\rfloor$ 為 6

    31 30 29 28 ... 10 9 8 7 6 5 4 3 2 1 0      // bit position
     0  0  0  0      0 0 0 0 1 0 0 1 1 1 1      // i=79
                             ^ 
                            msb 

可以用 GNU extension __builtin_clz 來得到 msb 前有幾個 0，透過

$31-clz(i)$ 可得到 msb 的位置，也就是

$\lfloor lg(i)\rfloor$ 的值。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(DDDD)); //DDDD = V | 1
}

Other Built-in Functions Provided by GCC 有對 __built-in_clz 進行說明，說明如下

Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

若輸入值為 0 則無定義，因此透過 V | 1 能確保值不為零。

Linux 核心原始程式碼

測驗四

測驗五

int ceil_ilog2(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 > GGG) + 1;  // GGG = 1      
}

這段程式碼的運作原理類似於測驗三的版本二，透過數值比較來決定要右移多少個位元，得出

$\lfloor lg(x)\rfloor$，由於函式要求出

$\lceil lg(x)\rceil$ ，因此要把結果進行加一再回傳。

注意到 x-- ，是為了要特別處理 2 的冪次方，分析如下:
若 x 為 2 的冪次方 ，則

$\lceil lg(x)\rceil =\lfloor lg(x)\rfloor =lg(x)$
若 x 非 2 的冪次方 ，則

$\lceil lg(x)\rceil =\lfloor lg(x)\rfloor +1$
透過 x-- ，這樣可以避免若 x 為 2 的冪次方結果不正確會多 1 的情形。

程式碼改進

int ceil_ilog2(uint32_t x)
{
    uint32_t r, shift;

-   x--;
+   x = (x == 0) ? 0 : 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 > GGG) + 1;  // GGG = 1      
}

原程式碼若輸入 0 ，則在 x-- 就會發生 underflow ，會導致結果不正確。
作業要求改善使其能處理 x = 0 的狀況，並仍是 branchless ，可以透過三元運算子來達到。

第四周測驗題

測驗一

測驗二