# linux2024-homework4
contributed by < [SHChang-Anderson](https://github.com/SHChang-Anderson) >
## 第三週測驗題
> [完整題目](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗一
#### 計算開平方根: (版本一)
```c
#include <math.h>
int i_sqrt(int N)
{
int msb = (int) log2(N);
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
`int msb = (int) log2(N);` 找到變數 `N` 的最高有效位 (most significant bit) 位置。
計算最高有效位的值存入變數 `a` 中。
進入迴圈，使用**逐位元掃描**的方法，從最高有效位開始，逐位檢查是否可以將對應的值加入到 `result` 中，而不會讓 `result` 的平方超過 `N`。此方法的特色在於相較於逐一數值嘗試開平方根近似的方式，利用了二進制表示的特性，每次只需要檢查一個位元，因此能夠更有效地近似計算出整數平方根。
#### 計算開平方根: (版本二)
```diff
int i_sqrt(int N)
{
+ int msb = 0;
+ int n = N;
+ while (n > 1) {
+ n >>= 1; // 將 n 右移一位，相當於除以 2
+ msb++; // 計數器加 1
+ }
- int msb = (int) log2(N);
int a = 1 << msb;
int result = 0;
while (a != 0) {
if ((result + a) * (result + a) <= N)
result += a;
a >>= 1;
}
return result;
}
```
與版本一不同於**不使用** `log2` 函式，而是使用迭代計算的方式找到最高位元。
這樣的優勢在於可以避免使用到浮點數運算，也可以在不支持 `log2` 的環境中運行。
#### 計算開平方根: (版本三)
這個版本的開方根利用 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 的概念實作開平方根。
首先若要對 $x$($x\geq0$) 做開平方根 ，可以假設 $x = N^2$ ， $N$ 即為欲求得的平方根數值，接著，將 $N$ 改寫為 2 的羃次和，即：
$N^2=(a_{n}+a_{n-1}+a_{n-2}+...+{a_0})^2, a_m=2^m\ or\ a_m=0$ 。
若將 $(a_{n}+a_{n-1}+a_{n-2}+...+{a_0})^2$ 做展開，透過矩陣觀察：
$\left[
\begin{array}{ccccc}
a_0a_0 & a_1a_0 & a_2a_0 & ... & a_na_0 \\
a_0a_1 & a_1a_1 & a_2a_1 & ... & a_na_1 \\
a_0a_2 & a_1a_2 & a_2a_2 & ... & a_na_2 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
a_0a_n & a_1a_n & a_2a_n & ... & a_na_n \\
\end{array}
\right]$
主對角線元素：
$\left[
\begin{array}{ccccc}
a_0a_0 & \\
& a_1a_1 & \\
& & a_2a_2 & \\
\ & \ & \ & \ddots & \ \\
& & & & a_na_n \\
\end{array}
\right]$
其餘元素：
$\left[
\begin{array}{ccccc}
& a_1a_0 & a_2a_0 & ... & a_na_0 \\
a_0a_1 & & a_2a_1 & ... & a_na_1 \\
a_0a_2 & a_1a_2 & & ... & a_na_2 \\
\vdots & \vdots & \vdots & \ & \vdots \\
a_0a_n & a_1a_n & a_2a_n & ... & \\
\end{array}
\right]$
將主對角線元素與其於元素分開討論可將原式整理成：
$N^2 = (\sum_{i=0}^n a_i)^2 = \sum_{i=0}^n a_i^2 + 2\sum_{0\leq i<j\leq n}a_ia_j$
其中， $\sum_{i=0}^n a_i^2$ 為對角線上的平方項，另外 $2\sum_{0\leq i<j\leq n}a_ia_j$ 為其餘的元素交叉相乘展開項。
接著將等式拆解為：
$$
\begin{align*}
\sum_{i=0}^n a_i^2 &+ 2\sum_{0\leq i<j\leq n}a_ia_j \\
&= a_n^2 + \sum_{i=0}^{n-1}a_i^2 + 2a_n\sum_{i=0}^{n-1}a_i + 2\sum_{0\leq i<j\leq n-1}a_ia_j
\end{align*}
$$
移項之後做觀察：
$$
\begin{align*}
\sum_{i=0}^n a_i^2 &+ 2\sum_{0\leq i<j\leq n}a_ia_j \\
&= a_n^2 + 2a_n\sum_{i=0}^{n-1}a_i + (\sum_{i=0}^{n-1}a_i^2 + 2\sum_{0\leq i<j\leq n-1}a_ia_j )
\end{align*}
$$
觀察括號內的數學式，可將 $(\sum_{i=0}^{n-1}a_i^2 + 2\sum_{0\leq i<j\leq n-1}a_ia_j)$ 改寫為：$(\sum_{i=1}^n a_i)^2$
最終整理得到：
$N^2 = a_0^2 + 2a_0(\sum_{i=1}^n a_i) + (\sum_{i=1}^n a_i)^2$
令 $P_m = a_n+a_{n-1}+...+a_m$
則所求 $N = P_0$ 。
接著將計算式整理成：
$N^2 = P_0^2 = a_0^2 + 2a_0(P_1^2) + (P_1)^2$
若推展成一般式可得：
$P_m^2 = a_m^2 + 2a_mP_{m+1} + P_{m+1}^2 = P_{m+1}^2 + a_m(2P_{m+1} + a_m)$
$P_m^2 = P_{m+1}^2+a_m(2P_{m+1} + a_m)$
可以將 $a_m(2P_{m+1} + a_m)$ 令為 $Y_m$ ，則 $P_m^2 = P_{m+1}^2+Y_m$ 。
若從從 $m=n$ 一路嘗試計算到 $m=0$ 每一輪透過 $Y_m$ 得到下一輪次的 $P_m^2$ 並測試 $P_m^2 \leq N^2$ 是否成立，最終即可找到所求。
然而，每輪計算 $P_m^2$ 的成本過高，若將 $N^2 - P_m^2$ 計算結果令為 $X_m$ ，則可推得 $X_{m} = N^2 - P_{m}^2 = N^2 - (P_{m+1}^2 +Y_{m})$ ，最終推得遞迴式： $X_{m}＝X_{m+1} - Y_{m}$ 。
這樣一來透過方程式 $Y_m = P_m^2 - P_{m+1}^2 = 2P_{m+1}a_m+a_m^2$ ，紀錄上一輪的 $P_{m+1}$ 來計算 $Y_m$ 以這樣的方式避免較高的運算成本。
為了實現演算法設計，進一步將 $Y_m$ 拆成 $c_m$ 與 $d_m$ ，得到：
$c_m = P_{m+1}2^{m+1}$
$d_m = (2^m)^2$
$Y_m=\left.
\begin{cases}
c_m+d_m & \text{if } a_m=2^m \\
0 & \text{if } a_m=0
\end{cases}
\right.$
可以藉由位元運算從 $c_m, d_m$ 推出下一輪 $c_{m-1}, d_{m-1}$ ，再利用 $c_{m-1}, d_{m-1}$ 計算出 $Y_m$ 最終推得 $a_m$ 。
* $c_{m-1}=P_m2^m=(P_{m+1}+a_m)2^m=P_{m+1}2^m+a_m2^m=\begin{cases}
c_m/2+d_m & \text{if }a_m=2^m \\
c_m/2 & \text{if }a_m=0
\end{cases}$
* $d_{m-1}=\dfrac{d_m}{4}$
綜合以上方法使用演算法尋求 $P_0$ ($a_n+a_{n-1}+...+a_0$) ，從 $P_n$ 的初始條件：
* $X_{n+1} = N^2$
* $X_{n} = X_{n+1} - Y_n$
* $X_{n} = X_{n+1} - (c_n + d_n)$
* $c_n = 0$
* $P_{n+1} = 0 \to c_n=0$
* $d_n = a_n^2=(2^n)^2= 4^n$
--------
```c
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 >>= AAAA) {
int b = z + m;
z >>= BBBB;
if (x >= b)
x -= b, z += m;
}
return z;
}
```
演算法中 `z` 對應到上述推導的 $c_n$, 而 `m` 對應到上述推導的 $d_n$。
由於初始的 $c_n = 0$, 將 `z` 設為 0:
`int z = 0;`
另一方面, $d_n = a_n^2 = (2^n)^2 = 4^n$ ，因此可以利用以下程式碼計算 `m`:
`int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL);`
------
```c
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= AAAA) {
int b = z + m;
z >>= BBBB;
if (x >= b)
x -= b, z += m;
}
```
在迴圈中， `int b = z + m;` ， `b` 對應到推導中的 $Y_m$ 。 而由上述推導 $c_{m-1}=\begin{cases}
c_m/2+d_m & \text{if }a_m=2^m \
c_m/2 & \text{if }a_m=0
\end{cases}$ 可知，無論 $a_m$ 結果為何，都需要將 $c_m / 2$ ，因此 `z >>= BBBB;` 就是 $c_m / 2$ 的實作， `BBBB` 應替換為 1 。
另外，由 $d_{m-1}=\dfrac{d_m}{4}$ 知道每一輪迴圈，需要將變數 `m` 除以 4， `m >>= AAAA` 應改為 `m >>= 2` 。
```c
if (x >= b)
x -= b, z += m;
```
以上條件判斷中， `if (x >= b)` 表 $X_{m+1} > Y_{m}$ 又 $X_{m}＝X_{m+1} - Y_{m}$ 則 $N^2 > P_m^2$ ，因此將 $a_m$ 加入 `z` 當中，因為 $c_{-1} = P_0 = a_n+a_{n-1}+...+a_0$ 因此最終所求即 `z` 。
------
#### 嘗試用 ffs / fls 取代 `__builtin_clz`
```c
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;
}
```
`__builtin_clz(x)` 函式回傳 `x` 的最高有效位前面連續的 `0` 位元的數量，那麼 `31 - __builtin_clz(x)` 就是最高有效位的位置。
同樣 `fls(x) - 1` 也可以找到最高有效位的位置，但 `fls()` 由索引值 1 開始計算，因此需要將 `fls(x) - 1`，從而計算需要左移多少位元才能得到最接近且不大於 `x` 的 2 的冪次數。
因此可以將程式碼改寫為：
```diff
int i_sqrt(int x)
{
if (x <= 1) /* Assume x is always positive */
return x;
int z = 0;
+ int shift = (fls(x) - 1);
+ for (int m = 1U << ((shift) & ~1U); m; m >>= 2) {
- 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;
}
```
#### 在 Linux 核心找出對整數進行平方根運算的程式碼
在 [lib/math/int_sqrt.c](https://github.com/torvalds/linux/blob/master/lib/math/int_sqrt.c)，找到整數平方根運算的程式碼：
```c
unsigned long int_sqrt(unsigned long x)
{
unsigned long b, m, y = 0;
if (x <= 1)
return x;
m = 1UL << (__fls(x) & ~1UL);
while (m != 0) {
b = y + m;
y >>= 1;
if (x >= b) {
x -= b;
y += m;
}
m >>= 2;
}
return y;
}
```
程式碼風格與實做原理與測驗一（版本三）類似，比較值得注意程式碼使用到 `__fls(x)` 來找到需要位移的位元數量，閱讀過去探討過關於 [ffs 及 __ffs 加雙底線與否的不同](https://hackmd.io/@sysprog/ByS9w_lHh#%E4%BB%BB%E5%8B%99%E7%B0%A1%E8%BF%B0) 了解`ffs` 及 `__ffs` (是否加雙底線) 的不同之處：參考 `bitops` 系列對外的介面: [arch/arc/include/asm/bitops.h](https://github.com/torvalds/linux/blob/master/arch/arc/include/asm/bitops.h) 中的註解得知：
* __XXX 系列: 以 index 0 索引，範圍為 0 ~ {length of input type - 1}
* XXX 系列: 以 index 1 索引，範圍為 1 ~ {length of input type}
由此可知使用 `__fls(x)` 來找到需要位移的位元數量，不需要 - 1 。
### 測驗二
#### `mod 10` 和 `div 10` 連續操作
本測驗針對正整數在相鄰描述進行 `mod 10` 和 `div 10` 操作的場景進行探討。若要優化這個計算情況,最直觀的方式是使用餘式定理。
根據餘式定理:
被除數 = (商 * 除數) + 餘數
對應到程式碼就是:
`tmp = (tmp / 10) * 10 + (tmp % 10)`
因此可以合併 mod 10 和 div 10 操作，改寫為以下程式碼：
```c
carry = tmp / 10;
tmp = tmp - carry * 10;
```
若使用 bitwise operation 實作以上除法，會發現由於 10 存在因數 5 並非 2 的羃，因此可能會產生誤差。
測驗中題到了 `tmp` 不可能會大於 19 ，因此只需要考慮 19~0 的情況即可。其原因為：
* tmp 是透過計算 `(b[i] - '0') + (a[i] - '0') + carry` 得到的。 `b[i]` 和 `a[i]` 分別是字符 '0' 到 '9' 之間的數字字符，對應的數值範圍是 0 到 9。
* 所以 (b[i] - '0') 和 (a[i] - '0') 的值範圍都是 0 到 9。
* 將兩個 0 到 9 之間的數相加,最大值為 9 + 9 = 18。
* 再加上最大可能的進位值 1,最大結果就是 18 + 1 = 19
接著，繼續針對方法繼續探究，針對此問題，提出了猜想：
* 我們的目標是找到一個適當的除數 q ，使得 tmp / q 的結果至少在小數點後一位是精確的。
* 假設最大的被除數是 n ，我們設 l 是一個比 n 小的非負整數。
* 現在考慮兩個數 ab 和 cd ，其中 a 和 c 是十位數 ， b 和 d 是個位數。
* 如果存在一個除數 q ，使得 cd / q 的結果在精確度範圍內，那麼 ab / q 的結果也應該在精確度範圍內。
假設：
* $n = ab$ ($a$ 是十位數 $b$ 是個位數)
* $l = cd$ ($c$ 是十位數 $d$ 是個位數)
----
以下證明上述猜想：
$a.b\leq\frac{n}{x}\leq a.b9\\
\Rightarrow\frac{n}{a.b9}\leq x\leq\frac{n}{a.b}$
分別對左右不等式進行探討：
$\frac{n}{a.b9}\leq x\leq\frac{n}{a.b}$
* 右不等式：
* $x\leq\frac{n}{a.b}$ 得知 $x\leq10$ 必然再精度以內。
* 左不等式：
* $\frac{n}{a.b9}\leq x$
接著討論 $c.d\leq\frac{l}{x}\leq c.d9$，若我們將 $\frac{n}{a.b9}$ 代入 $x$ 可將不等式改寫為：
$c.d\leq l\times\frac{a.b9}{n}\leq c.d9$
分別將 $l$ 與 $n$ 替換為 $cd$ $ab$ 可表現為：
$c.d\leq cd\times\frac{a.b9}{ab}\leq c.d9$
* 右不等式：
* $cd\times\frac{a.b9}{ab}\leq c.d9$ ， 首先將不等式改寫為： $cd\times\frac{a.b ＋ 0.09}{ab}\leq c.d + 0.09\Rightarrow cd\times (\frac{1}{10}+ \frac{0.09}{a.b})\leq c.d + 0.09$ ，又透過分配律可得到：$c.d + \frac{0.09cd}{ab}\leq c.d + 0.09$，由於 $ab > cd$ 因此 $\frac{0.09cd}{ab}\leq 0.09$ ，上述不等式必成立。
* 左不等式：
* $c.d\leq cd\times\frac{a.b9}{ab}\Rightarrow c.d \leq cd\times (\frac{1}{10}+ \frac{0.09}{a.b}) \Rightarrow c.d \leq c.d + \frac{0.09}{a.b}$ 明顯成立。
--------
由上述證明可得知，若 `tmp` 不可能會大於 19 ，只須透過不等式：
$1.9\leq \frac{19}{x}\leq 1.99\\
\Rightarrow 9.55\leq x\leq10$ 即可得知，除數介於 $9.55$ 至 $10$ 之間皆可程式中達到相同效果。
找除數的方法使用 bitwise operation $\frac{2^N}{a}$ 找到介於 $9.55\leq x\leq10$ 的除數，若欲處理得數字為$n$ 商式可以寫成 $\frac{an}{2^N}$ 。
$2^N=128, a=13,\frac{128}{13}\approx9.84$ 為一個可用的除數，由於 13 可以拆成 $13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0$ $2$ 的羃相加，因此範例程式中透過 `(tmp >> 3) + (tmp >> 1) + tmp` 得到 $\frac{13tmp}{8}$ 再將此式乘上 8 (向左位移 3 bits) 即可得到 $13tmp$ ，只要再將其除以 $128$ ($2^7$) 即可得到目標商式 $\frac{13tmp}{2^7}$ 。
#### 包裝後函式探討
```c
#include <stdint.h>
void divmod_10(uint32_t in, uint32_t *div, uint32_t *mod)
{
uint32_t x = (in | 1) - (in >> 2); /* div = in/10 ==> div = 0.75*in/8 */
uint32_t q = (x >> 4) + x;
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
*div = (q >> CCCC);
*mod = in - ((q & ~0x7) + (*div << DDDD));
}
```
`uint32_t x = (in | 1) - (in >> 2);`： 這行程式碼初始化 x。表達式 `(in | 1)` 確保 in 是奇數（將最低位設置為 1），然後減去向右移位 2 的 `in`（相當於將 `in` 除以 4），得到一個大約等於 $in \times 0.75$ ($\frac{3}{4}$) 的近似值。
`uint32_t q = (x >> 4) + x;` 相當於 $\frac{3}{4*2^4}in + \frac{3}{4}in$ 亦等於 $\frac{51}{64}in$ 若換算為小數約為 $0.79 \cdot in$ ，因此目前 `q` 值接近 $\frac{8}{10} \cdot in$ 。
```c
x = q;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
q = (q >> 8) + x;
```
接著不斷透過持續的 bitwise 操作使的 `q` 值持續逼近 $\frac{8}{10} \cdot in$ 。
`*div = (q >> CCCC);` 為了使商值 `*div` 正確被指定，`CCCC` 應替換為 `3` 得到 $\frac{8}{10}in \times
\frac{1}{8} = \frac{in}{10}$ 。
最後 `*mod = in - ((q & ~0x7) + (*div << DDDD)); ` 應為透過餘式定理的餘數計算。根據餘式定理:
餘數 = 被除數 - 除數\*商， `((q & ~0x7) + (*div << DDDD));` 計算的就是除數\*商的部份也就是 $quotient \cdot 10$ 。 `((q & ~0x7)` 的操作即 `q & 0xFFFFFFF8` 即將 `q` 最後三個位元清 0 ，這樣的作法使得目前 `q` 等價於 $quotient \cdot 8$ ，由於所求為 $quotient \cdot10 \Rightarrow quotient\cdot(8 + 2)$ 因此 `(*div << DDDD))` `DDDD` 應替換為 1 相當於 $quotient \cdot 2$ 以符合預期。
:::info
TODO：撰寫不依賴任何除法指令的 % 9 (modulo 9) 和 % 5 (modulo 5) 程式碼。
:::
### 測驗三
#### ilog2 以 2 為底的對數 (版本一)
```c
int ilog2(int i)
{
int log = -1;
while (i) {
i >>= 1;
log++;
}
return log;
}
```
* 首先將 `log` 設為 -1。這樣做是為了在輸入值為 0 時，函式回傳 -1。
* 接著進入一個 `while` 迴圈，當 `i` 不為 0 時持續執行迴圈體內的操作。
* 在迴圈內， `i` 右移一位 (`i >>= 1`)。這個操作相當於將 `i` 除以2。
* 每執行一次右移操作，就將 `log` 的值加1。
* 當 `i` 變為 0 時，迴圈終止。
* 最後，函式即可求得輸入值 `i` 的對數值並回傳。
#### ilog2 以 2 為底的對數 (版本二)
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= AAAA) {
result += 16;
i >>= 16;
}
while (i >= BBBB) {
result += 8;
i >>= 8;
}
while (i >= CCCC) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
這段程式碼每一次檢查一半的位元數量並進行 bitwise 位移，這種作法的優點是計算速度更快，因為它將對數值的計算分成了多個階段，每個階段只需要處理一小部分位元，而不是像前一種方法那樣逐位處理整個數值。
分段計算:這段程式碼將對數值的計算分成了多個階段,每個階段對應不同的位移量(16, 8, 4, 1)。這種做法可以加速計算過程,尤其是在處理大數值時。
這段程式碼將對數值的計算分成了多個階段，每個階段對應不同的位移量。可以觀察程式碼從最高 16 位元進行判別，接著是 8 位元 4 位元，直到最後一個位元為止。透過這樣的觀察我們可以知道 `AAAA` 、`BBBB` 、 `CCCC` 分別對映為 $2^{16}$ 、$2^{8}$ 、$2^{4}$ 。
可以發現這樣的方法就是尋找 `i` 最高有效位的位置。
#### Linux 核心 log2 的相關程式碼
在 [linux/log2.h](https://github.com/torvalds/linux/blob/master/tools/include/linux/log2.h) 中可以找到 log2 的相關實作。
```c
int __ilog2_u32(u32 n)
{
return fls(n) - 1;
}
int __ilog2_u64(u64 n)
{
return fls64(n) - 1;
}
```
可以看到 log2 使用到測驗一提到的 `fls` 也就是透過`fls(x) - 1` 找到最高有效位的位置達成與 ilog2 以 2 為底的對數 (版本二) 相同的效果。
### 測驗四
#### EWMA 理解
EWMA (指數加權移動平均) 是一種統計資料取平均的手法，其數學定義如下:
$S_t = \begin{cases}
Y_0& t = 0 \\
\alpha Y_t + (1 - \alpha)\cdot S_{t-1}& t > 0
\end{cases}$
其中:
- $S_t$ 為第 $t$ 個時間點的 EWMA 值
- $Y_t$ 為第 $t$ 個時間點的觀測值
- $\alpha$ 為歷史資料加權常數，介於0與1之間
當 $\alpha$ 值越大時，EWMA 會給予較多的權重於最近的觀測值，因此計算出的平均曲線會較為敏感，能夠快速反映最新的數據變化。反之，若 $\alpha$ 值較小，則 EWMA 會給予較多權重於歷史數據，計算出的平均曲線會較為平滑，變化也相對較小。
#### EWMA 實作
閱讀並理解測驗四中對於 EWMA 實作。首先，先觀察結構體 `ewma`：
```c
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
結構體中使用 `unsigned long` 除存所有參數，使用 2 的羃來除存所有參數以及權重。
```c
void ewma_init(struct ewma *avg, unsigned long factor, unsigned long weight)
{
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
avg->weight = ilog2(weight);
avg->factor = ilog2(factor);
avg->internal = 0;
}
```
`ewma_init` 函式用於初始化結構體中的參數。在函式內部，我們觀察到對要初始化的參數進行了檢查，確保其值是 2 的冪次方。這樣做是為了後續使用位元操作來提高效能，代替乘除法的運算。接著，將這些參數轉換為對數形式，以便後續的處理。
值得注意的是，透過程式碼中對於 2 的冪次方的檢測，可以得知實作希望使用定點數進行加權平均的計算。此外，在函式的註解中提到，`factor` 參數被用作準備定點數運算所需的平移值。
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << EEEE) - avg->internal) +
(val << FFFF)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
`ewma_add` 是實際執行 EWMA 計算的函式，其中 `internal` 對應到 $S_t$；而 `val` 對應到 $Y_t$。我推測 `(((avg->internal << EEEE) - avg->internal) + (val << FFFF)) >> avg->weight` 即為上述數學定義：$\alpha Y_t + (1 - \alpha)\cdot S_{t-1}$ 的實作方式。
我注意到當 `avg->internal` 為 0 時，函式會執行 `(val << avg->factor);`，也就是說當初始計算 EWMA 時尚未有任何資料，直接將目前時間點的觀測值加入。這時函式將 `val` 向左位移，因此我推測 `(val << FFFF)` 也應該將 `val` 向左位移，由此可知 `FFFF` 應該替換為 `avg->factor`。
接著，我繼續探究 `((avg->internal << EEEE) - avg->internal)` 程式碼部份。假設將 `EEEE` 暫時設置為變數 $x$，則由於 `weight` 以對數方式儲存 `(((avg->internal << EEEE) - avg->internal) + (val << FFFF)) >> avg->weight` 在數學上的意義為：$((S_{t-1} \cdot2^x - S_{t-1})+Y_t) \times \frac{1}{2^{weight}}$。然而目標數學方程式應該為：$\alpha Y_t + (1 - \alpha)\cdot S_{t-1}$，觀察可發現後者的 $\alpha$ 應為前式的 $\frac{1}{2^{weight}}$。因此，$(S_{t-1} \cdot2^x - S_{t-1}) \times \frac{1}{2^{weight}}$ 應該與 $(1 - \frac{1}{2^{weight}})\cdot S_{t-1}$ 等價，由此可推得 $x=weight$，因此 `FFFF` 應該替換為 `avg->weight`。
#### 在 Linux 核心原始程式碼找出 EWMA 的相關程式碼
在 [linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 可以找到 EWMA 實作程式碼。
```c
#define DECLARE_EWMA(name, _precision, _weight_rcp)
```
[linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 定義了 `DECLARE_EWMA` 巨集，這個巨集接受了三個參數， name(用於生成的 struct 和函式名稱)、 _precision (表示用於儲存小數部分的位元數)和 _weight_rcp (一個 2 的冪，決定了新舊值的加權)。
------
```c
struct ewma_##name { \
unsigned long internal; \
};
```
[linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 定義了一個結構體 ewma_，包含一個 unsigned long 型態的成員，用於儲存 EWMA 值。
--------
```c
static inline void ewma_##name##_init(struct ewma_##name *e) { \
BUILD_BUG_ON(!__builtin_constant_p(_precision)); \
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp)); \
/* \
* Even if you want to feed it just 0/1 you should have \
* some bits for the non-fractional part... \
*/ \
BUILD_BUG_ON((_precision) > 30); \
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp); \
e->internal = 0; \
}
```
ewma_init() 函式用於初始化結構實例，將 internal 設為 0。並使用了 BUILD_BUG_ON 巨集，在編譯時檢查 _precision 和 _weight_rcp 參數是否符合要求。
----
```c
ewma_##name##_read(struct ewma_##name *e) {
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
return e->internal >> (_precision);
}
```
`ewma_read()` 函式用於讀取 EWMA 值。由於 EWMA 實作使用了定點數運算，因此 internal 成員儲存了一個經過左移_precision 位的值。`internal` 成員儲存了經過放大的 EWMA 值(包含整數和小數部分)，而 `ewma_read()` 的右移操作則是為了將它縮小回原始的整數 EWMA 值。
----
```c
static inline void ewma_##name##_add(struct ewma_##name *e,
unsigned long val)
{
unsigned long internal = READ_ONCE(e->internal);
unsigned long weight_rcp = ilog2(_weight_rcp);
unsigned long precision = _precision;
BUILD_BUG_ON(!__builtin_constant_p(_precision));
BUILD_BUG_ON(!__builtin_constant_p(_weight_rcp));
BUILD_BUG_ON((_precision) > 30);
BUILD_BUG_ON_NOT_POWER_OF_2(_weight_rcp);
WRITE_ONCE(e->internal, internal ?
(((internal << weight_rcp) - internal) +
(val << precision)) >> weight_rcp :
(val << precision));
}
```
ewma_add() 函式是 EWMA 計算關鍵，用於將新值納入 EWMA 計算。它首先讀取 internal 值，根據 `_weight_rcp` 的值決定歷史資料與目前資料的加權。
#### 相關應用程式碼
[ath11k/core.h](https://github.com/torvalds/linux/blob/master/drivers/net/wireless/ath/ath11k/core.h) 找到 `DECLARE_EWMA(avg_rssi, 10, 8)` 定義了 EWMA 結構體，由 [linux/average.h](https://github.com/torvalds/linux/blob/master/include/linux/average.h) 可得知 `fixed-precision values` 為 10 而 $weight = \frac{1}{weight_{rcp}} = \frac{1}{8}$。
* **ath11k: 高通 IEEE 802.11ax 裝置的 Linux 驅動程式:**
根據 [Wireless Wiki](https://wireless.wiki.kernel.org/en/users/drivers/ath11k)，ath11k 是針對高通的 IEEE 802.11ax 無線網路裝置所設計的 Linux 驅動程式。它能夠支援在 SoC 類型裝置中的 AHB 匯流排和 PCI 接口。ath11k 基於 mac80211，這是 Linux 核心中用於無線網路裝置的通用框架。
* **`avg_rssi` 和 EWMA ：**
我參考了 [Received Signal Strength Indicator](https://en.wikipedia.org/wiki/Received_signal_strength_indicator) 一文來理解 RSSI。根據該資料，RSSI 是衡量設備從接收端接收訊號能力的指標，用於評估無線通訊中訊號的強度和品質。在 ath11k 的程式碼中，有一個名為 `avg_rssi` 的變數，被用來儲存指數加權移動平均值 (EWMA)。透過 EWMA，能夠平滑訊號強度的變化，提供更穩定的接收訊號強度指標 (RSSI)。
### 測驗五
#### `ceil_ilog2` 程式碼理解
`ceil_log2` 這個程式碼實現了一個函式，用於計算給定的 32 位元無號整數 $x$ 的最小次方指數值向上進位的結果。也就是說，對於傳入的參數 $x$ ，回傳最小的整數 n，滿足 $2^n \geq x$。
可以注意到函式的最開始將 x 減 1，這樣可以確保當 x 是 2 的冪次時，計算出的指數正確。
```c
r = (x > 0xFFFF) << 4;
x >>= r;
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
shift = (x > 0xF) << 2;
x >>= shift;
r |= shift;
```
接著根據以上程式碼的操作，我們可以觀察到類似於測驗三中的使用以 [2 為底的對數 (版本二)](https://hackmd.io/ahBQ35SOQyu1CmzVljikLQ?view#ilog2-%E4%BB%A5-2-%E7%82%BA%E5%BA%95%E7%9A%84%E5%B0%8D%E6%95%B8-%E7%89%88%E6%9C%AC%E4%BA%8C) 的二分搜尋法來找到最高位元位置。然而，與[測驗三程式碼](https://hackmd.io/ahBQ35SOQyu1CmzVljikLQ?view#ilog2-%E4%BB%A5-2-%E7%82%BA%E5%BA%95%E7%9A%84%E5%B0%8D%E6%95%B8-%E7%89%88%E6%9C%AC%E4%BA%8C)不同的是，這裡使用變數 `r` 來記錄位移量，而 `(x > 0xFFFF) << 4;` 的操作等價於以下程式碼：
```c
while (i >= 65536) {
result += 16;
i >>= 16;
}
```
在這裡，`(x > 0xFFFF)` 的結果是一個布林值。如果 `x` 的高 16 位元不為 0，則 `(x > 0xFFFF)` 的結果為 True，亦即等於 1。因此，位移量 `r` 被設定為 `1 << 4`，即 $16$，達到與[測驗三 log2 程式碼](https://hackmd.io/ahBQ35SOQyu1CmzVljikLQ?view#ilog2-%E4%BB%A5-2-%E7%82%BA%E5%BA%95%E7%9A%84%E5%B0%8D%E6%95%B8-%E7%89%88%E6%9C%AC%E4%BA%8C)相同的效果。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
值得注意的是，在程式碼中除了執行位移操作外，還將目前的位移量與變數 `r` 做了 $OR$ 運算，即 `r |= shift;`。由於位移量都是 2 的冪次方，因此這樣的 $OR$ 運算等同於對位移量進行加法操作（`result +=`）。因此，在進行位移後，程式碼將持續累加位移量，以找到最高位元位置。
```c
return (r | shift | x > GGG) + 1;
```
最終函式回傳，總位移量 + 1，然而若對照[測驗三 log2 程式碼](https://hackmd.io/ahBQ35SOQyu1CmzVljikLQ?view#ilog2-%E4%BB%A5-2-%E7%82%BA%E5%BA%95%E7%9A%84%E5%B0%8D%E6%95%B8-%E7%89%88%E6%9C%AC%E4%BA%8C)可發現，少了一個條件判斷：
```c
while (i >= 2) {
result += 1;
i >>= 1;
}
```
因此 `| x > GGG` 即判斷 $x$ 是否 $\geq$ $2$，也因此 `GGG` 應填入 $1$ 以符合預期。
#### 改進程式碼
試想上述程式碼若傳入參數 $x = 0$ 時，程式碼的第一行， `x--` 會將 `x` 值改變為 `0xFFFFFFFF` ，這樣一來，會使得接下來的迴圈以及條件判斷不符合預期，因此需要對此做修正。
簡單的修正方法即為加入 `if` 條件判斷，避開 $x=0$ 時做減法，然而這樣的方式並不符合 [branchless](https://sdremthix.medium.com/branchless-programming-why-your-cpu-will-thank-you-5f405d97b0c8) 。
我嘗試將程式碼做以下更動：
```diff
int ceil_ilog2(uint32_t x)
{
uint32_t r, shift;
+ x = x - (x > 0);
- 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 > GGG) + 1;
}
```
加入 `x = x - (x > 0);` 後使得在 $x>0$ 時才會產生布林值 1 ，達到減 1 的效果，並仍是 [branchless](https://sdremthix.medium.com/branchless-programming-why-your-cpu-will-thank-you-5f405d97b0c8) 。
## 第四週測驗題
> [完整題目](https://hackmd.io/@sysprog/linux2024-quiz4)
### 測驗一
#### Population count 程式碼理解
[population count](https://en.wikichip.org/wiki/population_count) 簡稱 popcount 或叫 sideways sum，是計算數值的二進位表示中，有多少位元是 1。
閱讀到關鍵程式碼：
```clike=
n = (v >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
n = (n >> 1) & 0x77777777;
v -= n;
```
不了解為何 `n = (v >> 1) & 0x77777777` 即可將數值分為四個位元一個單位做減法，並透過 `v -= n` 即可求得 $v - \left \lfloor{{\dfrac{v}{2}}}\right \rfloor$ 。因此我將數學式列出，最一開始，傳入值 v 即為 $2^{31}b_3 + 2^{30}b_2 + 2^{29}b_1 + ... + 2^0b_0$ 而將 `v >> 1` 可得 $0 + 2^{30}b_2 + 2^{29}b_1 + ... + 2^1b_1$ 。
而我們可以得知 `(v >> 1) & 0x77777777;` 結果為：
```
0 b_31 b_30 b_29 b_28 b_27 ... b_4 b_3 b_2 b_1
& 0 1 1 1 0 1 0 1 1 1
---------------------------------------------------
0 b_31 b_30 b_29 0 b_27 ... 0 b_3 b_2 b_1
```
寫成數學式為：
$(0+2^{30}b_{31}+2^{29}b_{30}+2^{28}b_{29}) + (0+2^{26}b_{27}+2^{25}b_{26}+2^{24}b_{25})+ ... + (0+ 2^{2}b_3+ 2^{1}b_2+ 2^{0}b_1)$
若持續重複執行 `n = (n >> 1) & 0x77777777;
v -= n;` 可以分別得到：
$(0+0+2^{29}b_{31}+2^{28}b_{30}) + (0+0+2^{25}b_{27}+2^{24}b_{26})+ ... + (0+ 0+2^{1}b_3+ 2^{0}b_2)$
$(0+0+ 0+2^{28}b_{31}) + (0+0+0+2^{24}b_{27})+ ... + (0+ 0+ 0+ 2^{0}b_3)$
因此，若以四項為單位做相減即可得到：
$(2^3b_3 + 2^2b_2 + 2^1b_1 + 2^0b_0) -
(2^2b_3 + 2^1b_2 + 2^0b_1) - (2^1b_3 + 2^0b_2) - 2^0b_3$
並對應到以**每 4 個位元 (nibble) 為一個單位**計算 1 的個數。
接著透過一系列位移以及 bitmask 操作可得所求的 popcount 值。
#### Hamming Distance
```c
int hammingDistance(int x, int y)
{
return __builtin_popcount(x ^ y);
}
```
Hamming Distance 是指這兩個數字對應位元的不同位置的個數。例如：數字 3 (二進制為 $0011$ )和數字 5 (二進制為 $0101$ )的漢明距離為 2，因為它們在第一位和第三位不同。
在程式碼中，使用了位元運算子 XOR( $\oplus$ ) 來找出兩個數字在哪些位置不同。對於任何兩個位元，只有當它們不同時， XOR 的結果才會是 1。因此， $x \oplus y$ 的結果會是一個數字，其二進制表示中 1 的位置就是 x 和 y 不同的位置。
接著程式使用 `__builtin_popcount` 函式來計算 $x \oplus y$ 中有多少個 1，也就是 x 和 y 有多少個不同的位元。這個函數的實作方式是直接對輸入的數字計算其二進制表示中 1 的個數，效率相當快。因此，這一行程式碼實際上就是在快速計算出 x 和 y 的漢明距離。
```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` 陣列中所有數字之間的漢明距離總和。需特別注意的是，程式中重複考慮了兩個數字之間的距離，因此最終結果為總距離的兩倍。為了將結果除以 2，使用右移操作符將總和向右移動1位。因此，`AAAA` 應填入 1。
#### Total Hamming Distance 程式碼改進
從位元展現的樣貌，觀察 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|1|**0**|
|Input 17|1|0|0|0|**1**|
首先，我們觀察第 0 個位元位置。在這個位置上，數字 7、5、17 都是 1，而數字 10 是 0。進一步探究 Hamming Distance：
```graphviz
digraph so
{
rankdir=TB;
1->0 [dir=none]
}
```
```graphviz
digraph so
{
rankdir=TB;
1 [label="1";]
11 [label="1";]
111 [label="1";]
0 [label="0";]
1->0 [dir=none;color=red]
11->0 [dir=none;color=blue]
111->0 [dir=none;color=orange]
{rank= 1 11 111}
{rank= 0}
}
```
從上圖可理解為：每個 1 位元可以與 1 個 0 位元產生距離為 1 的 Hamming Distance。因此，由於有 3 個 1 位元，總 Hamming Distance 為 $1 \times 3$ 。
接下來，我們觀察第 1 個位元位置：
```graphviz
digraph so
{
rankdir=TB;
1 [label="1";]
0 [label="0";]
00 [label="0";]
1->0 [dir=none]
1->00 [dir=none]
{rank= 0}
}
```
```graphviz
digraph so
{
rankdir=TB;
1 [label="1";]
11 [label="1";]
0 [label="0";]
00 [label="0";]
1->0 [dir=none;color="red"]
1->00 [dir=none;color="red"]
{rank= 0}
11 ->0 [dir=none;color="blue"]
11 ->00 [dir=none;color="blue"]
}
```
在第 1 個位元位置上，數字 7 和 10 都是 1，而數字 5 和 17 是 0。觀察上圖可理解為：每個 1 位元可以與 2 個 0 位元產生距離為 1 的 Hamming Distance。因此，由於有 2 個 1 位元，總 Hamming Distance 為 $2 \times 2$。
總結來說，可以計算每個位置上的 1 位元數量，並將每個位置的 1 位元數量乘以 0 位元數量，以求得 Total Hamming Distance。
根據以上方法實作改進後的程式碼：
```c
int totalHammingDistance_(int* nums, int numsSize)
{
int total = 0;
for (int i = 0;i < 32;i++) {
int ct = 0;
for (int j = 0; j < numsSize;j++)
ct += ((nums[j] >> i) & 1);
total += ct * (numsSize - ct);
}
return total;
}
```
撰寫程式驗證其正確性：
> commit [3e675c3](https://github.com/SHChang-Anderson/Lab4/commit/3e675c35c13b45d2a54f16167e8b72b8d672b941)
使用 `perf` 分析其效能差異，針對 10000 筆數字進行 Total Hamming Distance 計算。
改進前：
```
Performance counter stats for './totalHammingDistance':
1,141,370,997 cycles
0.425123945 seconds time elapsed
0.421050000 seconds user
0.003972000 seconds sys
```
改進後：
```
Performance counter stats for './totalHammingDistance_':
4,986,285 cycles
0.003329801 seconds time elapsed
0.000000000 seconds user
0.003289000 seconds sys
```
可以發現改進後的程式碼大幅減少了 clock cycles 數量，同時也縮減了執行時間。
### 測驗二
#### Remainder by Summing digits
為了在不使用除法的情況下計算某數除以另一個數的餘數，使用了模同餘的概念。
當除數為 3 時，我們可以觀察到 $1 \equiv 1 (mod \ \ 3)$ 和 $2 \equiv -1 (mod \ \ 3)$。 根據 $ac \equiv bd (mod \ \ m )$ 的性質，我們可以進行以下推導：
$2^k \equiv \begin{cases}
1 (mod \ \ 3), \ \ k \ \text{為偶數}\\
-1 (mod \ \ 3), \ \ k \ \text{為奇數}\\
\end{cases}$
當我們將 $n$ 以二進位表示時，可以寫為 $b_{n-1}b_{n-2}b_{n-3}...b_1b_0$。
根據前述推導，我們得知當 $k$ 為偶數時，同餘為 1；當 $k$ 為奇數時，同餘為 -1。因此，我們可以得到以下表達式：
$n=b_{n-1} \cdot 2^{n-1} + b_{n-2} \cdot 2^{n-2} + \ldots + b_3 \cdot 2^{3} + b_2 \cdot 2^{2} + b_1 \cdot 2^{1} + b_0 \equiv \ldots - b_3 + b_2 - b_1 + b_0 \ (mod \ 3)$
接著，我們使用以下定理進行化簡：
$popcount(x \land \overline{m}) - popcount(x \land m) = popcount(x \oplus m) - popcount(m)$
因此，`n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)` 可以寫為 `n = popcount(n ^ 0xAAAAAAAA) - 16`。
然而，以上計算結果的範圍會落在 -16 至 16 之間。考慮到希望餘數為正數的情況，我們需要加上一個 3 的倍數以確保餘數在同餘情況下為正數。
至於為何要加上 39 ? 參閱 《[Hacker's Delight](https://web.archive.org/web/20180517023231/http://www.hackersdelight.org/divcMore.pdf)》中的說明：
>We want to apply this transformation again, until n is in the range 0 to 2, if possible. But it is best to avoid producing a negative value of n, because the sign bit would not be treated properly on the next round. A negative value can be avoided by adding a sufficiently large multiple of 3 to n. Bonzini’s code, shown in Figure 10–21, increases the constant by 39. This is larger than necessary to make n nonnegative, but it causes n to range from –3 to 2 (rather than –3 to 3) after the second round of reduction. This simplifies the code on the return statement, which is adding 3 if n is negative. The function executes in 11 instructions, counting two to load the large constant.
在文中指出，將常數增加了 39。這個值比僅使非負數所需的常數值更大，可使得在第二輪計算後，值落在 -3 到 2 的範圍內(而非 -3 到 3)，也因此簡化了程式碼，只需在 n 為負數時加 3 即可。
另一種方法是直接將 0 到 32 的所有數字除以 3 得到的餘數事先儲存在一個 lookup table 中，這樣就可以直接透過查表的方式找到對應的餘數。程式碼如下所示：
```c
int mod3(unsigned n)
{
static char table[33] = {2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1, 2, 0, 1 };
n = popcount(n ^ 0xAAAAAAAA);
return table[n];
}
```
#### 井字遊戲程式碼理解
此程式實現的是一個井字遊戲的變體，該變體將遊戲目標從傳統的在3x3棋盤上實現三個連續的棋子，擴展到了在任何八條可能的直線上達到三個連續的棋子。這使得玩家的策略更加多樣化，因為一步棋可能會影響多條直線。
程式中設計了 `available_moves[]` 陣列，此陣列即為 3x3 井字遊戲上的九個位置選擇，因此我們可以看到 `play_random_game` 函式中，每做出一個選擇將其選擇從陣列中移除：
```c
uint32_t move = available_moves[i];
available_moves[i] = available_moves[n_moves - 1];
```
實作方式就是將選擇的走法用最後一個可用的走法來替換，然後將最後一個可用的走法移到了被選擇的走法所在的位置。
在 `board |= move_masks[move];` 這行程式碼中，將選定的走法 `move` 對應的連線狀態更新到了玩家的棋盤狀態中。在這個井字遊戲變體中，棋盤狀態不是按照傳統的九宮格形式表示，而是以8條可能的連線來表示。這意味著玩家的棋盤狀態存儲了對應於這8條連線的狀態，而不僅僅是傳統的棋子擺放狀態。
對於 `board |= move_masks[move];` 這行程式碼，`move_masks[move]` 取得了選定走法 `move` 對應的連線狀態，然後將它與玩家的棋盤狀態 `board` 做位元或運算，從而將選定走法的影響更新到了玩家的棋盤狀態中。由於每個 `move_masks` 元素都包含了對應位置下棋可能影響的所有連線，因此這個操作有效地更新了玩家棋盤狀態中的所有可能連線。
```c
static const uint32_t move_masks[9] = {
0x40040040, 0x20004000, 0x10000404, 0x04020000, 0x02002022,
0x01000200, 0x00410001, 0x00201000, 0x00100110,
};
```
`move_masks` 陣列中的每個元素代表了在將棋子放置到特定位置後，對於所有可能連線狀態的影響。每個元素的二進位表示描述了在該位置放置棋子後，連線狀態發生變化的情況。
以 `0x40040040` 為例，用圖示來進行說明：
考慮 `0x40040040` 九宮格棋盤中為左上角 (0) 的選擇：
||1|2|3|
|-|-|-|-|
|**1**|==**0**==|1|2|
|**2**|3|4|5|
|**3**|6|7|8|
此位置將有三種可能連線：
||1|2|3|
|-|-|-|-|
|**1**|==**0**==|==1==|==2==|
|**2**|3|4|5|
|**3**|6|7|8|
對應到 `board` 二進位表示即：
0**1**11 0000 0000 0000 0000 0000 0000 0000
||1|2|3|
|-|-|-|-|
|**1**|==**0**==|1|2|
|**2**|==3==|4|5|
|**3**|==6==|7|8|
對應到 `board` 二進位表示即：
0000 0000 0000 0**1**11 0000 0000 0000 0000
||1|2|3|
|-|-|-|-|
|**1**|==**0**==|1|2|
|**2**|3|==4==|5|
|**3**|6|7|==8==|
對應到 `board` 二進位表示即：
0000 0000 0000 0000 0000 0000 0**1**11 0000
`0x40040040` 以二進位可表示為：
0**1**00 0000 0000 0**1**00 0000 0000 0**1**00 0000 玩家棋盤狀態與其做 $or$ 運算可更新棋子擺上棋盤 0 位置後對連線狀態的影響。
```c
static inline uint32_t is_win(uint32_t player_board)
{
return (player_board + BBBB) & 0x88888888;
}
```
勝利的條件判斷即 `player_board` 以四個位元為單位出現 0111 即判斷該玩家獲勝，可以看到程式碼將 `(player_board + BBBB)` 與 `0x88888888` 做 $and$ 運算，由此可知，當出現 0111 時需要將棋結果轉為 1000 ，而將 0111 + 1 即可達成此效果，因此 `BBBB` 應填入 `0x11111111` 。
#### Modulo 7 程式碼理解
:::info
TODO
:::
### 測驗三
#### XTree
`treeint.c` 為二元樹測試程式，用來測量在不同的操作下，如插入、查找和刪除，二元樹的性能表現。
* `treeint_ops` 結構，該結構包含指向各種樹操作函式的指標。
* `xt_ops` 為 `treeint_ops` 的實例 ，並將其函式指標設定為特定的實作函式。
`xtree.[ch]` 二元搜尋樹的實現，它採用了一些特定的策略來保持樹的平衡。
二元樹的結構定義包含 `xt_tree` 以及 `xt_node` ，值得注意的是在 `xt_node` 中加入了 `hint` 作為平衡參數。
程式使用不同函式實現二元樹的不同功能：
* xt_create 函數創建一個空的樹。
* xt_destroy 和 __xt_destroy 函數用來遞迴釋放樹中所有節點的記憶體。
* xt_rotate_left 和 xt_rotate_right 函數用於節點的左旋和右旋操作，這是平衡樹的關鍵操作之一。
* xt_update 函數根據節點的平衡因子進行相應的旋轉操作，以維持樹的平衡。
* __xt_find 和 __xt_find2 函數實現了在樹中查找特定鍵值的節點。
* __xt_insert 和 xt_insert 函數實現了向樹中插入新節點的功能。
樹的刪除操作：
刪除操作相對複雜，尋找替代節點（右子樹的最小節點或左子樹的最大節點）並進行替換。
```c
if (xt_right(del)) {
struct xt_node *least = xt_first(xt_right(del));
if (del == *root)
*root = least;
xt_replace_right(del, AAAA);
xt_update(root, BBBB);
return;
}
if (xt_left(del)) {
struct xt_node *most = xt_last(xt_left(del));
if (del == *root)
*root = most;
xt_replace_left(del, CCCC);
xt_update(root, DDDD);
return;
}
```
* 函式首先檢查被刪除的節點 `del` 是否有右子節點 `（xt_right(del)）`。
* 若存在，它會找到右子樹中最小的節點`（xt_first(xt_right(del))）`，這個最小節點將會取代要被刪除的節點。
* 如果被刪除的節點是根節點`（del == *root）`，則將根節點更新為這個最小節點 `（*root = least）`。
* 接著，函式呼叫 `xt_replace_right` 找到的最小節點來替換被刪除的節點。因此 `AAAA` 應該替換為 `least`。
* 最後，對替換後的新樹結構進行 `xt_update` ，以維持樹的平衡。由於替換操作後，`least` 節點被移動到了 `del` 的位置，而 `least` 的原位置現在由它的右子節點所取代，針對原位置的節點進行更新，因此`BBBB` 應替換為 `xt_right(least)`。
同樣的，若刪除的節點有左子節點， `CCCC` 應該被替換為 `most`，表示將 `most` 節點放到 `del` 節點的位置。
如果被刪除的節點 `del` 有左子節點，會找到這個左子樹中的最大節點 `most` 來替代 `del`。而 `DDDD` 應替換為 `xt_left(most)` 。
最後，當欲刪除的節點沒有子節點時分為兩種情況進行處理：
* 節點為根節點：如果要刪除的節點 `del` 正好是根節點，直接將根節點指標設置為 `NULL`，樹將變為空。
* 節點非根節點：如果 `del` 不是根節點，那麼首先找到 `del` 的親代節點 `parent` ，接著判斷 `del` 是其親代節點的左子節點還是右子節點。如果 `del` 是左子節點，則將 `parent` 的左子節點指針設置為 `NULL`。如果 `del` 是右子節點，則將 `parent` 的右子節點指針設置為 `NULL`。此舉使得節點從二元樹中斷開。
* 平衡更新：`xt_update(EEEE, FFFF)` 來更新樹的平衡。 `EEEE` 應傳入 `root`。由於刪除 `del` 後，需要重新平衡的是 `del` 的親代節點 `parent`。因此 `FFFF` 應該是 `parent` 節點。
Sign in with Wallet
Connect another wallet