2024q1 Homework4 (quiz3+4)

contributed by < shiang1212 >

第三週測驗題

測驗一

這個測驗的目的是計算 input 的平方根(捨去小數)，最簡單的方法是從 reslut = 0 開始測驗，測驗 reslut * reslut > input 是否成立，成立的話，此時的 reslut - 1 就是我們要的答案；不成立的話就 reslut++ 繼續往上測驗。

與版本一和版本二的概念相似，兩方法的測驗方法如下：

int a = 1 << msb;
int result = 0;
while (a != 0) {
        if ((result + a) * (result + a) <= N) // 測驗
            result += a;
        a >>= 1;
    }

相較於簡單的方法用 reslut++，這個方法是用 reslut += 2^n 逼近，其中 n = {msb, msb - 1, msb - 2, ..., 1, 0}，測驗 reslut + 2^n * i + 2^n <= N 是否成立，成立的話就 reslut += 2^n。每輪測驗完就讓 n--，直到 n == 0，以下為範例。

input = 50
msb = 5
-----------------------------------------
result = 0, a = 32 (2^5)  |  測驗不成立，a >>= 1
result = 0, a = 16 (2^4)  |  測驗不成立，a >>= 1
result = 0, a = 8  (2^3)  |  測驗不成立，a >>= 1
result = 0, a = 4  (2^2)  |  測驗成立，result += a, a >>= 1
result = 4, a = 2  (2^1)  |  測驗成立，result += a, a >>= 1
result = 6, a = 1  (2^0)  |  測驗成立，result += a, a >>= 1
result = 7, a = 0         |  a == 0，結束測驗

測驗三

版本一：

透過不斷對輸入進行右移，計算輸入的 leftmost set bit 位置。

nth bit  7654 3210      
14:      0000 1110
              ^ 
              leftmost set bit 在第 3 個 bit => log(14) = 3

考慮到輸入為

$2^0=1$ 的情況，所以 log 初始成 -1。但也可以改寫成以下：

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

版本二：

使用二分搜尋的作法，不斷切半判斷輸入是否大於

$2^{16}、2^8、2^4、2^2、2^1$ 並右移 16、8、4、2、1。使用二分搜尋的概念讓該方法可以得到與版本一相同的答案，但運算速度比版本一更快。

若 "|" 左側數值大於 0，則進行右移

0110 1001 0111 0001|1110 1111 0000 0110
(右移16，result+=16)
0000 0000 0000 0000 0110 1001 0111 0001
------------------------------------------
0000 0000 0000 0000 0110 1001|0111 0001
(右移8，result+=8)
0000 0000 0000 0000 0000 0000 0110 1001
------------------------------------------
0000 0000 0000 0000 0000 0000 0110|1001
(右移4，result+=4)
0000 0000 0000 0000 0000 0000 0000 0110
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 01|10
(右移2﹑result+=2)
0000 0000 0000 0000 0000 0000 0000 0001
------------------------------------------
0000 0000 0000 0000 0000 0000 0000 000|1
("|" 左側數值小於 0，不右移)
0000 0000 0000 0000 0000 0000 0000 0001
------------------------------------------
result = 30 // leftmost set bit 

版本三：

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

相似於版本一，只是反過來計算輸入的 leading zero 個數，反推 leftmost set bit 的位置。

0000 0000 0000 0000 1110 1111 0000 0110

leading zero 個數：16
leftmost set bit = 31 - 16 = 15 // 第 15 個 bit

測驗五

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

第四週測驗題

測驗一

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

這段程式碼計算 nums 裡任兩個有號整數的漢明距離(Hamming distance)，使用兩個 for 迴圈走訪 nums 裡的所有數值，並計算每一種組合的漢明距離。

wiki 中漢明距離的介紹：

兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。

程式碼的第 6 行用於計算漢明距離，首先 nums[i] 與 nums[j] 做 XOR 操作可以得到一串由 0 和 1 組成的數列，其中 1 代表兩個數值二進位下對應的 bit 不同，再用 __builtin_popcount 求該數列 bit 為 1 的個數，就可以得到 nums[i] 與 nums[j] 的漢明距離。

num_1 = 10100
num_2 = 01111
----------------- 
// 兩者做 XOR 得到 num_3
num_3 = 11011
----------------- 
// 計算 num_3 的 bit 為 1 的個數
hamming_distance = __builtin_popcount(num_3)

// hamming_distance = 4，即為 num_1 與 num_2 二進位對應 bit 不同的個數

了解如何計算兩數值之間的漢明距離後，只要將所有組合的漢明距離加總就能達到該題的要求。但該程式碼在累加的時候會重複計算，舉例來說，在計算 num_1 與 num_2 之間的漢明距離時，程式碼會額外多累加一次 (即hamming_distance(num_1, num_2) 與 hamming_distance(num_2, num_1))，所以最後要再除以 2，也就是右移 1，所以 AAAA = 1。