2024q1 Homework4 (quiz3+4)

contributed by < aftuta85 >

第 3 週測驗題

測驗一

測驗二

測驗三

版本二：

static size_t ilog2_v2(size_t i)
{
    size_t result = 0;
    while (i >= 65536) {
        result += 16;
        i >>= 16;
    }
    while (i >= 256) {
        result += 8;
        i >>= 8;
    }
    while (i >= 16) {
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

版本二程式碼分別透過 while 位移 16、8、4、1 位元來計算出 MSB 在第幾個位置來求出 ilog2 的值。
程式碼中分別透過檢查 >= 65536、256、16、2 來決定要位移多少位元。
這邊解釋為什麼是檢查 65536，65536 的二進為為 1 0000 0000 0000 0000，將其減一來看更清楚，65535 = FFFF FFFF FFFF FFFF，也就是說若大於等於 65536 就可以直接位移 16 位元。

舉例來說，i = 70000，二進位如下：
0001 0001 0001 0111 0000 // 檢查是否大於等於 65536 (1 0000 0000 0000 0000)
=> result = 16, i >>= 16
0000 0000 0000 0000 0001 // i < 256, i < 16, i < 2
=> return result

由版本二程式碼可以知道所需要計算的目標為 MSB，因此可以用 __builtin_clz() 來實作，如版本三：

static int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

__builtin_clz() 回傳從左邊數來連續的 0 的數量。以 32 位元為例，若 v = 8 (0b100)，__builtin_clz() 會回傳 28，因此 MSB 就是 31 - 28 = 3。

在傳入 __builtin_clz() 中的 v 為了避免 v = 0 的情況因此使用 V | 1 來防止造成未定義行為。

passing 0 as the argument to "__builtin_ctz" or "__builtin_clz" invokes undefined behavior

測驗五

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 > 1) + 1;       
}

上述程式碼透過判斷 x 是否大於 0xFFFF、0xFF、0xF、0x3 來進行相對應的 >> 位元數，分別為 16、8、4、2 位元。在透過 r 紀錄位移的量，也就是 x - 1 之後的 log2 的值，由於是要計算 ceil 因此最後在 + 1。
在裡面的 x-- 會遇到當 x = 0 時造成的計算錯誤，因此可以改用下面作法：

int ceil_ilog2(uint32_t x)
{
-  x--;
+  x -= !!x;
}

ceil_ilog2 做法跟將 x - 1 後透過計算 MSB (測驗三的 ilog32) 後在加 1 有什麼不同的地方嗎?

static int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

static int ceil_ilog2_v2(uint32_t x)
{
    x -= !!x;
    return ilog32(x) + 1;
}

第 4 週測驗題

測驗一

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0; i < numsSize; i++)
        for (int j = 0; j < numsSize; j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total >> 1;
}

假設 nums 有三個整數，上述程式碼執行方式如下：
nums[0] ^ nums[0]
nums[0] ^ nums[1]
nums[0] ^ nums[2]
nums[1] ^ nums[0]
nums[1] ^ nums[1]
nums[1] ^ nums[2]
nums[2] ^ nums[0]
nums[2] ^ nums[1]
nums[2] ^ nums[2]

從上面執行順序可以看出，兩個整數的比較會重複，因此最後結果須除 2 (total >> 1)

第一個改進可以調整 j 的起始位置，從 i + 1 開始，這樣元素的比較就不會重複計算，改動如下：

int totalHammingDistance(int* nums, int numsSize)
{
    int total = 0;;
    for (int i = 0; i < numsSize; i++)
        for (int j = i + 1; j < numsSize; j++)
            total += __builtin_popcount(nums[i] ^ nums[j]); 
    return total;
}

若是透過每個 nums 的 bit 0、bit 1、…、bit n 來比對的方式來計算，可寫成下面程式碼：

int totalHammingDistance(int* nums, int numsSize) {
    int res = 0;
    // 比較 32 個 bits
    for (int i = 0; i < 32; i++) {
        int count = 0;
        for (int j = 0; j < numsSize; j++) {
            count += (nums[j] >> i) & 1;
        }
        res += count * (numsSize - count);
    }
    return res;
}

測驗二

測驗三