# 2024q1 Homework4 (quiz3+4) contributed by < `shiang1212` > ## [第三週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3) ### 測驗一 這個測驗的目的是計算 `input` 的平方根(捨去小數)，最簡單的方法是從 `reslut = 0` 開始測驗，測驗 `reslut * reslut > input` 是否成立，成立的話，此時的 `reslut - 1` 就是我們要的答案；不成立的話就 `reslut++` 繼續往上測驗。 與版本一和版本二的概念相似，兩方法的測驗方法如下： ```c 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。但也可以改寫成以下： ```diff 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 ``` #### 版本三： ```c 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 ``` ### 測驗五 ```c 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; } ``` ## [第四週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4) ### 測驗一 ```c= 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](https://zh.wikipedia.org/zh-tw/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB) 中漢明距離的介紹： >兩個等長字符串之間的漢明距離（英語：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`。