# 2024q1 Homework4 (quiz3+4)
contributed by < [yy214123](https://github.com/yy214123) >
## 第 3 週測驗題
### 測驗 `1`
版本一及版本二程式邏輯一致，差別在於版本二不依賴 [log2](https://man7.org/linux/man-pages/man3/log2.3.html)，首先是求出輸入 $N$ 其二進制的 MSB 位置，接著令 `a` 為 $2^{msb}$，作為猜測 $N$ 之平方根的初值，最後透過 while 迴圈逐步調整輸出。

重新整理 $Y_m=c_m+d_m$

$Y_m$ 的定義如下：
$Y_m=P_m^2-P_{m+1}^2$

$P_m$ 的定義如下：
$P_m=(a_n+a_{n-1}+a_{n-2}+...+a_{m+1}+a_{m})=P_{m+1}+a_m$

當 $a_m = 2^m$ 時：
$P_m=P_{m+1}+a_m=P_{m+1}+2^m$
則 $P_m^2=(P_{m+1}+2^m)^2= \color{red}{P_{m+1}^2+2^{m+1}\cdot P_{m+1}+2^{2m}}$

所以 $Y_m=P_m^2-P_{m+1}^2=\color{red}{(P_{m+1}^2+2^{m+1}\cdot P_{m+1}+2^{2m})}-P_{m+1}^2=2^{m+1}\cdot P_{m+1}+2^{2m}$

令 $c_m=2^{m+1}\cdot P_{m+1} , d_m=2^{2m}$
則 $Y_m=c_m+d_m$

又 $c_m=2^{m+1}\cdot P_{m+1}$，所以 $c_{m-1}=2^{m}\cdot P_{m}$
根據 $P_m$ 之定義可得 $c_{m-1}=2^{m}\cdot (P_{m+1}+a_m)$

當 $a_m = 2^m$ 時：
$c_{m-1}=2^{m}\cdot (P_{m+1}+a_m)=2^{m}\cdot (P_{m+1}+2^m)=2^m \cdot P_{m+1}+2^{2m}$
可得 $c_{m-1}= c_m/2+d_m$

先前已知 $X_m=N^2-P_m^2$
故 $X_{n+1}=N^2-P_{n+1}^2$
又所求為 $a_n+,,,+a_0$
所以 $X_{n+1}=N^2$

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

首先判斷欲開平方根之數是否為 `0` 或 `1`，因為這兩個數字開根號即為其本身。
程式中的 `b = z + m ` 其實就等同於上方所推導的 $Y_m=c_m+d_m$
### 測驗 `2`
這個測驗屬於大數運算的範疇，在呼叫 `str_add` 前，應該先將兩個字串反轉。首先看到：

`int tmp = (b[i] - '0') + (a[i] - '0') + carry;`

在 [c99 6.3.1 Arithmetic operands](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) 中有討論到有關 integer promotions 有關的議題，故可得知在每個字元在減掉 `'0'` 後會變成對應的整數值，將索引相同的字元相加後除以 10 將商數及餘數儲存。

### 測驗 `3`
版本一的 `ilog2` 函式，是靠著不斷的右移來完成，一次右移 1 bit 直到為 0。

版本二的 `ilog2` 函式，首先可以看到輸入的型別是 `size_t`，其 typedef 在 `stddef.h` 中，其實等同於 long unsigned int，故可以得知該函式最大接受 $2^{32}-1$ 作為輸入，而下方的四個 while 迴圈其功能可快速判斷輸入的大小，一次右移更多 bits 來完成實作。

版本三的方式對應到教材 [你所不知道的 C 語言：數值系統](https://hackmd.io/@sysprog/c-numerics)，只要算高位有幾個 0's bits. 再用 31 減掉即可。這邊以簡易的 8 bits 無號數範例說明：
> $16_{(10)}=00010000_{(2)}$
> $19_{(10)}=00010011_{(2)}$
> 而 $00010000_{(2)}$，其高位有 3 個 0's bits，7 減掉 3 為 4，即為 $ln 16$。
> 而 $00010011_{(2)}$，其高位亦 3 個 0's bits，7 減掉 3 為 4，即為 $ln 16$。
> 故可知只考慮最高位數過來首次出現的 1 即可，後面的不會影響取 $ln$ 的解。
### 測驗 `4`
### 測驗 `5`
剛開始看這題時，對於：

x > 0xFFFF
x > 0xFF
x > 0xF
x > 0x3

有蠻多疑惑的，為什麼 x 是與這些數字比較，而非其他數字呢？

輸入的 `x` 為 32 位元無號整數，而 `0xFFFF` 其二進制為較低的 16 位元均為 1，所以如果 `x` 大於 `0xFFFF` 則表示 `x` 至少須 17 位元來表示，可如下表示其範圍：

$2^{16}<=x<=2^{32}-1$

故將 `x` 右移 **16 位元**並不會遺失高位元的資訊。

接著第二步判斷 右移 16 位元後的 `x` 是否大於 `0xFF`，這相當於去判斷原始的 `x` 至少須 25 位元來表示，可如下表示其範圍：

$2^{24}<=x<=2^{32}-1$

故再將 x 右移 **8 位元**也不會遺失高位元的資訊。

第三步判斷範圍：
$2^{28}<=x<=2^{32}-1$

第四步判斷範圍：
$2^{30}<=x<=2^{32}-1$

而中間巧妙的運用 `r |= shift` 來紀錄，而由於在程式的最一開始進行了 `x--`，將 `x` 的原始值是 2 的冪也考慮進去。

:::success
改進程式碼，使其得以處理 x = 0 的狀況，並仍是 branchless
:::
基於測驗 `3`， 我想也能用 `__builtin_clz` 進行改進，並且可以處理 x = 0 的狀況，改進後的程式如下：

int ceil_ilog2_v2(uint32_t x)
{
    x--;
    return (32 - __builtin_clz(x | 1));
}

觀摩其他學員後，我發現我誤會處理 x = 0 的狀況這句話的意義了，因為 x 是無號數，若將其扣掉 1 ，會變成 16 進制的 `0xFFFFFFFF`，此時函數會回傳 32 ，但實際上 $ln 0$ 是沒有意義的，參考 [vax-r](https://hackmd.io/@vax-r/linux2024-homework4#%E6%B8%AC%E9%A9%97%E4%BA%94)的作法，可如下修改：

-   x--;
+   x -= !!x;

假如 `x` 為 0，`!x` 為 1，所以 `!!x` 為 0，此時不會執行 -1，所以不會導致函式的輸入變成 `0xFFFFFFFF` ，如果 `x` 是大於 0 的數，則 `!x` 為 0，所以 `!!x` 為 1，此時就會正確地將函式的輸入扣掉 1。
___
## 第 4 週測驗題
### 測驗 `1`
理解 `popcount_naive()` 的程式邏輯說明花了很長時間，在 [2024q1 第 4 週測驗題測驗 1](https://hackmd.io/@sysprog/linux2024-quiz4#%E6%B8%AC%E9%A9%97-1) 中提到：

`n = (v >> 1) & 0x77777777` : 將輸入數值 `v` 除以 2，得到 $\lfloor \cfrac{v}{2}\rfloor$。

起初對 `& 0x77777777` 這個運算很不解，紙筆追蹤後也確實不是想像中的除以 2，後來留意到前面的描述：**每 4 個位元 (nibble) 為一個單位**，才恍然大悟。
:::success
解釋程式碼運作原理。
:::
考慮下列程式碼：

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

挖空的 ``AAAA`` 應填入 `1`。原因是在雙層迴圈中會多計算一次，所以最後的 `total` 會是兩倍的 Total Hamming Distance，故執行 `>> 1` 將其除以 2 後才會是正確答案。
:::success
不依賴 popcount，嘗試以上述歸納的規則，針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。
:::
### 測驗 `2`
以前在學離散數學時，一直不知道模同餘這個議題有什麼應用場景，這個測驗蠻有趣的，平常我們在算數學，要求餘數直接長除法就好，但對電腦來說使用除法器的會增加成本。
### 測驗 `3`