# 2024q1 Homework4 (quiz3+4)
contributed by < [`56han`](https://github.com/56han/lab0-c) >
## 第 3 週測驗題
[2024q1 第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗 `1`

$Y_m = \begin{cases}
c_m + d_m, & \text{if } a_m = 2^m \\
0, & \text{if } a_m = 0
\end{cases}$

在每次迴圈更新 $c_m$、$d_m$ 來計算 $Y_m$ 進而推得 $a_m$
$c_{m-1} = {P_m}{2^{m}} = (P_{m+1} + a_{m})2^{m} = P_{m+1}2^{m} + a_{m}2^{m} =
\begin{cases}
\frac{c_{m}}{2} + d_{m} & \text{if } a_{m} = 2^{m} \\
\frac{c_{m}}{2} & \text{if } a_{m} = 0
\end{cases}$

$d_{m-1} = \frac{d_{m}}{4}$

透過閱讀數學算式，進而得到幾個重點：
* 函式中 `z` 即是 $C_m$，而 `m` 即是 $d_m$，`b` 即是 $Y_m$，`x` 則是代表前一輪的差值，也就是 $X_{m+1}$。
* 函式中的迴圈每次迭代時 `m` 往右位移 2 位，是在表示上面公式中的 $d_{m-1} = \frac{d_{m}}{4}$。
* `b = z + m; ` 表示 $Y_m = c_m + d_m$。
* `if` 條件是判斷：當 $X_{m+1}$ 比 $Y_{m}$ 大時，則更新其值。

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 >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

#### 延伸問題 - 嘗試用[第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2)提到的 ffs / fls 取代 __builtin_clz，使程式不依賴 GNU extension

* `__ffs()` 函數的目的是找到參數 (unsigned long) 中**最低位**的 1 所在的位置（從 0 開始計算）。
* 將`__ffs()` 函數改寫成下面的 `fls()` 函數的目的是找到參數 (unsigned long) 中**最高位**的 1 所在的位置（注意：從 1 開始計算）。
* `__builtin_clz()` 為 GCC 的內建函式，功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。

所以將 `BITS_PER_LONG - fls(x)` 即可得到 `__builtin_clz(x)`。

static inline unsigned long fls(unsigned long x)
{
    int num = 32;
    if(!x)
        return 0;
    if ((x & 0xffff0000) == 0) {
        num -= 16;
        x <<= 16;
    }
    if ((x & 0xff000000) == 0) {
        num -= 8;
        x <<= 8;
    }
    if ((x & 0xf0000000) == 0) {
        num -= 4;
        x <<= 4;
    }
    if ((x & 0xc0000000) == 0) {
        num -= 2;
        x <<= 2;
    }
    if ((x & 0x80000000) == 0) {
        num -= 1;
        x <<= 1;
    }
    return num;
}

因此可以將 `i_sqrt()` 改寫成以下

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 >>= 2) {
+    for (int m = 1UL << (fls(x)-1 & ~1UL); m; m >>= 2) {
        int b = z + m;
        z >>= 1;
        if (x >= b)
            x -= b, z += m;               
    }
    return z;
}

### 測驗 `2`
### 測驗 `3`
考慮 `ilog2()` 可計算以 2 為底的對數，且其輸入和輸出皆為整數。以下是其一可能的實作: (版本一)
透過一次又一次的右移(除以 2 )，直到 `i=0`，去計算 i 以 2 為底時有多少位數。

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

改寫為以下程式碼: (版本二)
透過右移的方式去計算 i 以 2 為底時有多少位數。
:::info
我認為這裡的 while 可以改成 if，因為 i 透過右移會越來越小，因此不會進入相同迴圈中，只會往下走，進入別的判斷式中。
:::

static size_t ilog2(size_t i)
{
    size_t result = 0;
    while (i >= (1<<16)) { //2^16
        result += 16;
        i >>= 16;
    }
    while (i >= (1<<8)) { //2^8
        result += 8;
        i >>= 8;
    }
    while (i >= (1<<4)) { //2^4
        result += 4;
        i >>= 4;
    }
    while (i >= 2) {
        result += 1;
        i >>= 1;
    }
    return result;
}

亦可運用 GNU extension `__builtin_clz` 來改寫，注意輸入若是 0 則無定義： (版本三)
透過 `31-__builtin_clz()` 找到最高位數，即是取 log 以後的值。
>`__builtin_clz()` 為 GCC 的內建函式，功能為找到 x 最高位數前面有幾個 0 ， x 為 0 時，未定義。

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

### 測驗 `4`

### 測驗 `5`
延伸測驗 3，已知輸入必為大於 0 的數值 (即 x > 0)，以下程式碼可計算 $\lceil \log_2(x)\rceil$，也就是 ceil 和 log2 的組合並轉型為整數：

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 - 1`，是為了對於 2 的冪的數值也能夠正確計算對數。
`shift = (x > 0xFF) << 3;` 表示，若 x > 15 則為 `1 << 2`，否則為 `0 << 2`。
大部分和測驗 3 類似，當我們看到以下片段

shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;

首先判斷 `x > 0xFF` ，並使用 shift 記錄要移動多少。
`x >>= shift;` 即是測驗 3 的 `i >>= 16;`，`r |= shift;` 即是 `r = r + shift;` 之意。

最後 return 可拆成3個部份看

return (r | shift | x > 1) + 1;  

1. `r | shift ` 即是 `r = r + shift;` 之意
2. 判斷 x 是否還有剩，因為前面`shift = (x > 0x3) << 1;` 會忽略 `x = 0x2` 的情況。
3. 最後再 +1 作為取上界 (ceil) 。

## 第 4 週測驗題
[2024q1 第 4 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)

### 測驗 `1`
此題是 [LeetCode 477. Total Hamming Distance](https://leetcode.com/problems/total-hamming-distance/submissions/1219875025/) ，透過兩個for 迴圈可以逐一比較兩個數字之間的 Hamming Distance，最後要除以2 (右移1位)，因為重複計算ab和ba。

GCC 提供對應的內建函式:
>`__builtin_popcount(x)`: 計算 x 的二進位表示中，總共有幾個 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 >> 1;
}

#### 延伸問題 - 不依賴 popcount，嘗試以上述歸納的規則，撰寫出更高效的程式碼。
從 popcount 角度出發，時間複雜度就被限制在 $O(n^2)$。
以下嘗試從位元展現的樣貌，觀察 Total Hamming Distance 的規則。

| n'th bit | 4 | 3 | 2 | 1 | 0 |
| -------- | --| --| --| --| --|
| input 7 | 0| 0| 1| 1| 1|
| input 5 | 0| 0| 1| 0| 1|
| input 10 | 0| 1| 0| 0| 1|
| input 17 | 1| 0| 0| 0| 1|

1. 第 0 個 bit 觀察 :
全部都是 1 -> Hamming Distance = 0
2. 第 1 個 bit 觀察 :
1 有一個，其餘皆為 0
可以直接用單個 bit 判斷 Hamming Distance (1)* (numsize - 1)
3. 第 2 個 bit 觀察 :
1 有兩個，其餘皆為 0
Hamming Distance (2)* (numsize - 2)

以 bit 找規則:
>所有 Number 中從第 0 個 bit 開始計算全部該 bit 的 Hamming Distance ，在全部累加起來就是 Total Hamming Distance。

可以改寫成以下程式碼，其中：
* `(nums[i] >> bit) & 1` 判斷 `nums[i]` 該 bit 是否為 1
* `bitCount` 統計出所有數字的該 bit 為 1 有幾個
* `bitCount * (numsSize - bitCount)` 統計該 bit 的 Hamming Distance

int totalHammingDistance(int* nums, int numsSize) {
    int total = 0;
    for (int bit = 0; bit < 32; bit++) {
        int bitCount = 0;
        for (int i = 0; i < numsSize; i++) {
            bitCount += (nums[i] >> bit) & 1;
        }
        total += bitCount * (numsSize - bitCount);
    }
    return total;
}

### 測驗 `2`
:::info
我理解 `n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 可以寫為 `n = popcount(n ^ 0xAAAAAAAA) - 16` ，其中也可以理解「我們要將它加上一個足夠大的 3 的倍數」，但為何是選擇加上39？使其為 `n = popcount(n ^ 0xAAAAAAAA) + 23;`
:::

int mod3(unsigned n)
{
    n = popcount(n ^ 0xAAAAAAAA) + 23;
    n = popcount(n ^ 0x2A) - 3;
    return n + ((n >> 31) & 3);
}

### 測驗 `3`