2024q1 Homework4 (quiz3+4)

contributed by <YeeeLiang>

第三周測驗題

測驗一

int i_sqrt(int x)
{
    if (x <= 1) /* Assume x is always positive */
        return x;

    int z = 0;
-   for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= AAAA) {
+   for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 2) {
        int b = z + m;
-       z >>= BBBB;
+       z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

測驗二

進行除以 10 的除法和餘數運算，將 CCCC 設置為除法移位的位元數（例如 32 位），將 DDDD 設置為餘數遮罩的位元數（例如 32 位）。

#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
    uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
    uint32_t q = (x >> 4) + x;
    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

-   *div = (q >> CCCC);
+   *div = (q >> 28);
-   *mod = in - ((q & ~0x7) + (*div << DDDD));   
+   *mod = in - ((q & ~0x7) + (*div << 28));  
}

測驗三

AAAA、BBBB 和 CCCC 需要根據不同的情況設置適當的值，來確保 ilog2 函數的運作。而這些值應該是 2 的冪次方。

考慮到每個 while 迴圈將 i 右移不同的位數，計算每次迴圈中右移的位數，並設置相應的值。在第二版本中，我們使用了 1UL << n 來計算 2 的冪次方，其中 n 是右移的位數。

以下是修改後的程式碼：

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

測驗四

在這個 EWMA 實作中，EEEE 和 FFFF 代表位移量，這些位移量需要確保加法和位移操作的結果不會溢出。

對於 EEEE，它代表的是左移的位數，確保不會溢出，因此改寫成 avg->factor。因為 avg->factor 是初始化時由 ilog2(factor) 計算得來的。

對於 FFFF，它代表的是右移的位數，應確保不會溢出，因此改寫成 avg->weight。同樣地，avg->weight 是在初始化時由 ilog2(weight) 計算得來的。

測驗五

這段程式碼是用來計算一個32位的無符號整數的對數（logarithm）的向上取整值。在原始碼中，GGGG 被替換為將 x 轉換為二進制後的位數，以得到正確的向上取整值。這是因為向上取整的概念是將小數部分捨去，如果最後一次右移操作將有非零的結果，那麼就需要再加 1。

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 > GGGG) + 1;    
+   return (r | shift | x > (x >> 1)) + 1; 
}

第四周測驗題

測驗一

測驗二

測驗三