# 2024q1 Homework4 (quiz3+4)
contributed by < `vestata` >
## [第 3 周測驗題](https://hackmd.io/@sysprog/linux2024-quiz3)
### 測驗一
> [commit 401bd93](https://github.com/vestata/linux2024-homework4/commit/401bd937bcade0193b8bf36074d46a6c8fd3cc54)
這段程式碼中的 `log2(N)` 函數用來計算數字 `N` 的以 2 為底的對數。
在這個 `i_sqrt` 函數中，`log2(N)` 用於找出 `N` 的最高有效位（most significant bit, msb）。這是因為 `N` 的平方根絕不會大於 `N` 本身的二進位數值。舉例來說，如果 `N` 是 16，其二進位表示為 10000（5位），則其平方根不會超過 $2^log(N) = 16$。因此，通過 `log2(N)`，我們可以找到一個**大約**的起始點來進行平方根的計算，從而減少計算次數。
在 `i_sqrt` 函式中，`a` 被設置為 `1 << msb`，即 `2` 的 `msb` 次方。這是對 `N` 進行二進位搜索的起始點，然後逐步右移（`a >>= 1`），進行逼近計算，直到找到最接近 `N` 的平方根為止。
log 函數通常返回一個浮點數，因此這裡將結果轉換為整數（使用 (int) 強制類型轉換），依賴於標準數學庫，並涉及浮點運算。
> [版本二](https://github.com/vestata/linux2024-homework4/commit/c2327bc0a7bb895bb19d11b994b5ae3b1cc5a56b) 過程中直接在整數的二進位表示上操作，不涉及浮點運算。
#### 整理數學式
##### 自 [Digit-by-digit calculation](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation) 中:
- 先簡單舉例：
令 $Z = 10X + Y$, 平方根為 10 位數的狀況。
$Z = (10X + Y)^2 = 100X^2 + 20XY + y^2$
- 這時候使用 digit-to-digit algo
1. 先找 x 使用：每一輪 $x*2$ 使其滿足 $x^2 <= (Z >> 2)$
2. 找到最大之 X 帶入找 Y
- 延伸到所有狀況：
$N = (a_1 + a_2 + a_3 + ... a_n)^2$
又
$(a_1 + a_2 + a_3 + \dots + a_n)^2 =$
$a_1^2 + 2a_1a_2 + a_2^2 + 2(a_1 + a_2)a_3 + a_3^2 + \dots + a_{n-1}^2 + 2 \left( \sum_{i=1}^{n-1} a_i \right) a_n + a_n^2 =$
$a_1^2 + [2a_1 + a_2] a_2 + [2(a_1 + a_2) + a_3] a_3 + \dots + \left[ 2 \left( \sum_{i=1}^{n-1} a_i \right) + a_n \right]a_n$
- 再根據上面的算法由 $a_1...a_{m-1}$逐一去猜。
- 令 $a_1...a_{m-1}$ 已被猜到 $a_m$ 那一項便會是 $Y_m = [2P_{m-1} + a_m]a_m$，其中 $P_{m-1}$ 是前面已備猜到的部份。
- 所以要猜 $a_m$ 會滿足遞迴式 $X_m = X_{m-1} - Y_m$
<!--
```graphviz
digraph S{
node[shape=record]
tmp[label="a_1 |a_2|...|<a1> a_(m-1)| <a2>a_m|...|||a_n"]
tmp2[label="2 * 前面的猜測"]
}
```
-->
##### 在 Binary numeral system (base 2)之下略有不：
$N^2 = (a_n + ... + a_0)^2, a_m=2^m\,or\,a_m$
根據 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3) 的推導：
$P_m = a_n + a_{a-1} + ... + a_m$
$P_m = a_n + a_{a-1} + ... + a_0$ 為平方根 $N$
所以便是針對 $P_m$ 逐一嘗試：
由於無法每一輪檢驗 $N^2 - P_{m}^2$ 成本過高，所以可以用跟上一輪的差值做比較。
再將 Y_m 做細分成 $c_m,d_m$
$c_m = P_{m+1}2^{m+1}$
$d_m = (2^m)^2$
在每一輪會更新 $c_m, d_m$
$c_{m-1} = P_m 2^m = \left( P_{m+1} + a_m \right) 2^m = P_{m+1} 2^{2m} + a_m 2^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} = \frac{d_m}{4}$
最終條件會是 $c_{-1} = P_02^0 = P_0 = N$
#### 程式修正
`__builtin_clz` 之功能為回傳從前面數有多少 0
> Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
1. 針對 [第 2 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz2) 之中的 `ffs` (從後面數有多少 0) 所採用 binary search 的方法做出與 `__builtin_clz` 相同功能的 `fls`
2. 針對提供分支和無分支 (branchless) 的實作，目前不確定如何實作。
> [commit 8bd78f4](https://github.com/vestata/linux2024-homework4/commit/8bd78f466272976a20c4e63513609ef2e61fde86)
在看了 linux kernel 中的 `fls` 使用發現這邊的誤用，這邊做了修正。
```diff
int z = 0;
- for (int m = 1UL << ((31 - fls(x)) & ~1UL); m; m >>= 2) {
+ for (int m = 1UL << ((fls(x) - 1) & ~1UL); m; m >>= 2) {
int b = z + m;
z >>= 1;
```
> [commit 29b0769](https://github.com/vestata/linux2024-homework4/commit/29b076981b44d573a954a4eb79a2e1e392dec5e6)
#### Linux 核心 `linux/block/blk-wbt.c`
在以下程式碼有提到：
```c
static void rwb_arm_timer(struct rq_wb *rwb)
{
struct rq_depth *rqd = &rwb->rq_depth;
if (rqd->scale_step > 0) {
/*
* We should speed this up, using some variant of a fast
* integer inverse square root calculation. Since we only do
* this for every window expiration, it's not a huge deal,
* though.
*/
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
} else {
/*
* For step < 0, we don't want to increase/decrease the
* window size.
*/
rwb->cur_win_nsec = rwb->win_nsec;
}
blk_stat_activate_nsecs(rwb->cb, rwb->cur_win_nsec);
}
```
`blk-wbt.c` 代表 Buffered writeback throttling 是一調節 I/O 的技術。策略如下：
- 在一個定義的時間窗口內監控延遲。
- 如果該時間窗口內的最小延遲超過某個目標值，則增加 scaling step ，並將 queue 深度縮小 2 倍。然後將時間窗口縮小到 100 / sqrt(調節步驟 + 1)。
- 對於任何沒有確鑿延遲數據的窗口，保持現狀。
- 如果延遲看起來不錯，則減小 scaling step 。
直接對應 `sqrt()` 程式：
```c
if (rqd->scale_step > 0) {
rwb->cur_win_nsec = div_u64(rwb->win_nsec << 4,
int_sqrt((rqd->scale_step + 1) << 8));
} else {
rwb->cur_win_nsec = rwb->win_nsec;
}
```
rwb->win_nsec 會初始為 100ms，但是這邊這邊跟敘述的 `100 / sqrt(調節步驟 + 1)` 實作不一樣，分別對 `rwb->win_nsec << 4`，`(rqd->scale_step + 1) << 8` ，為何要位移不知道為何作用。
:::info
TODO 去翻 block 的 commit message
:::
:::info
閱讀〈Analysis of the lookup table size for square-rooting〉和〈Timing Square Root〉，嘗試撰寫更快的整數開平分根運算程式。
:::
### 測驗二
### 測驗三
#### 解釋程式碼運作原理
- [ ] 版本一
使用最直觀的方式，使用 while loop 不斷對 i 除以 2 得出 $log_2(i)$
- [ ] 版本二
> [commit e66f2c9](https://github.com/vestata/linux2024-homework4/commit/e66f2c939765396a44738319e6b46ea8bf9dc8ef)
以 binary search 針對不同大小 i 可以一次做多位數的計算，增加其速度。
- [ ] 版本三
> [commit cb2ec77](https://github.com/vestata/linux2024-homework4/commit/cb2ec770ab8d734e23b5b30f82e046bcc6801b10)
使用 GNU extension `__builtin_clz(x)`
> Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
所以它會回傳 x 前面有多少位元為 0。如果講他視為以下格式 `__builtin_clz(x)` 便會是 n 等價於它最高位的非 0 元素是 (n-1) = 31 - n，便會是 log(n)
| 31 | 30 | ... | n | n-1 | ... | 0 |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 0 | ... | 0 | 1 | ... | 1 |
:::warning
TODO: 分析上述實作手段的指令延遲
:notes: jserv
> 好的，以下為實作 [name=vestata]
:::
#### clock_gettime() 測量
以下分析三種實作手段的延遲差異：
> [commit 61732ea](https://github.com/vestata/linux2024-homework4/commit/61732ea61f8b0d6433030f6f297ddc11a74c67e8)
1. 修改原本的程式，加入 Designated Initializers：
```c
int main(){
Log2Impl impls[] = {
{.func = ilog2, .file_name = "out_ilog2.txt"},
{.func = ilog2_2, .file_name = "out_ilog2_2.txt"},
{.func = ilog32, .file_name = "out_ilog32.txt"}
};
for (int j = 0; j < sizeof(impls) / sizeof(impls[0]); j++) {
FILE *fp = fopen(impls[j].file_name, "w");
struct timespec start, end;
int i;
for (i = 1; i < 1000000 && i; i++) {
clock_gettime(CLOCK_MONOTONIC, &start);
impls[j].func(i);
clock_gettime(CLOCK_MONOTONIC, &end);
long long time = (long long) (end.tv_sec * 1e9 + end.tv_nsec) - \
(long long) (start.tv_sec * 1e9 + start.tv_nsec); \
fprintf(fp, "%u, %lld\n", i, time);
}
fclose(fp);
}
return 0;
}
```
2. 新增 gnuplot 腳本
3. 修改 Makefile
對 1~5000 的資料：
對 1~10000 的資料：
對 1~1000000 的資料：
可以觀察到 ilog32 的速度跟穩定度相較 ilog2, ilog_binary 都很高，因為使用 `__builtin_clz(x)` 比起其他兩個方法還省去 bitwise 的操作，還可以快速找到 msb 直接算出 log2 答案。ilog2 在時間上的表現是最差的辦多的噪點，使用最基本的除法方式，效率會很慢。ilog_binary 因為其 binary search 的性質在較大的數值會有比較好的表現。
在這個實驗我發現使用 log2 的時間會有許多噪點，目前這些噪點出現的原因我尚未釐清。我在 gnuplot 時為了清楚的繪圖，使用 threshold 去捨棄 200ns 以上的數值。
:::info
為何有如此多噪點呢？
先思考是否為計時程式導致的問題？
:::
#### Perf 測量
所以我更新了我實驗的方式，改為使用 perf ，我使用命令 `perf stat --repeat=5 -e task-clock ./2024w3q3 method x` 有定義三種方法 0, 1, 2 分別對應上述三種方法，x 定義為 `ilog(x)` 的參數，x 大小定義為 1 - 10000，並平均五次測試的結果。
接下來撰寫了一個 bash 腳本以分別完成對三種方法的測量輸出 `csv` 檔案。
```bash
executable_name="./2024w3q3"
output_file_prefix="perf_output_function_"
if [ "$#" -ne 1 ]; then
echo "Usage: $0 <function_index>"
exit 1
fi
function_index="$1"
output_file="${output_file_prefix}${function_index}_r5.csv"
rm -f "$output_file"
for i in $(seq 1 10000)
do
echo "Measuring performance for function index $function_index with input: $i"
perf stat --repeat=5 -e task-clock -o temp_perf_data -- "$executable_name" $function_index $i 2>/dev/null
task_clock=$(grep 'task-clock' temp_perf_data | awk '{print $1}')
echo "$i, $task_clock" >> "$output_file"
done
echo "Performance measurement for function index $function_index completed."
```
此次實驗得出的結果使用 gnuplot 繪出以下：
雖然使用 perf 中的 task-clock 沒有出現像上一個實驗的噪點，但是圖像中顯示 ilog32() 沒有像理論上產生如此大的優勢。我回頭思考使用 perf 作為時間測量的正確性。
perf 的 task-clock 是以一個程式為單位，但是如今我們測試目標是 ilog2() ，是一個計算速度非常快的函式，其時間只會佔執行程式非常小的部份，所以使用 perf 之 task-clock 不會是正確的選擇。
#### 實驗結論
所以實驗結果還是依據還是使用 `clock_gettime()` 但是噪點原因還在分析中。但就算有噪點，但是因為 ilog2() 運算速度極快，對整個程式影響不大。
附上三種方法 perf 10000 筆資料平均的比較：
```
The average time for ilog2() is 0.268591 ms
The average time for ilog2_2() is 0.264863 ms
The average time for ilog32() is 0.262433 ms
```
#### Linux 核心原始程式碼
在 [include/linux/log2.h](https://github.com/torvalds/linux/blob/712e14250dd2907346617eba275c46f53db8fae7/include/linux/log2.h#L31) 中可以見到它取 `ilog2` 使用的方式是調用 fls() 來進行，它可以快速取的最大的非 0 位置， `fls(x) - 1` 便是 $log_2(x)$
我們可以看到它分定義針對 32 位元架構 `__ilog2_u32` 與 64 位元架構的 `__ilog2_u64`，皆是採用 fls 的作法。
之後會在主要 `ilog2(n)` 巨集被調用
```c
#define ilog2(n) \
( \
__builtin_constant_p(n) ? \
((n) < 2 ? 0 : \
63 - __builtin_clzll(n)) : \
(sizeof(n) <= 4) ? \
__ilog2_u32(n) : \
__ilog2_u64(n) \
)
```
`__builtin_constant_p` 是 GCC 編譯器提供的一個內建函數，用來檢查其參數是否是在編譯時已知的常數表達式。如果參數是一個常數表達式，則 `__builtin_constant_p` 返回 1；如果參數不是常數表達式，則返回 0。而常數表達式表示該便書在編譯期間不會改變，提高程式碼的效率和執行速度。
如果是常數便進入 `(n) < 2 ? 0 : 63 - __builtin_clzll(n)) :` 如果 n 是 0 或是 1 便直接回傳 0，再來檢查 n 的大小如果他是 32 位元 ((sizeof(n) <= 4)) 便使用 __ilog2_u32(n)，若不是則使用 __ilog2_u64(n) 。
### 測驗四
#### EWMA
原理詳見 [第 3 週測驗題](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-4)
觀察 EWMA 的可能實作中提到：
- 主要針對降低 rounding 所帶來的誤差。
- 透過 Scaling factor 使 internal 可以更準確的運算。
- 有 `ewma_read()` 來輸出 internel 的值，不要直接存取結構體中的 internel。
##### struct ewma
```c
/* Exponentially weighted moving average (EWMA) */
struct ewma {
unsigned long internal;
unsigned long factor;
unsigned long weight;
};
```
- internal：$S_t$
- factor：scaling factor 用途
- EWMA 結構可以表示的最大平均數值。這個值由公式 `ULONG_MAX / (factor * weight)` 決定，其中 ULONG_MAX 是 unsigned long 數據類型能夠表示的最大值。這個公式顯示了 scaling factor 和權重如何共同影響可表示的最大平均值。
- weight：$\alpha$ 用於衰減舊數據影響的指數權重
##### `ewma_init`
```c
if (!is_power_of_2(weight) || !is_power_of_2(factor))
assert(0 && "weight and factor have to be a power of two!");
```
限制為 2 的冪主要是基於性能和計算效率的考慮。
##### `ewma_add()`
* @avg: Average structure
* @val: Current value
```c
struct ewma *ewma_add(struct ewma *avg, unsigned long val)
{
avg->internal = avg->internal
? (((avg->internal << avg->weight) - avg->internal) +
(val << avg->factor)) >> avg->weight
: (val << avg->factor);
return avg;
}
```
這邊 `ewma_add()` 按照上述取平均的統計手法，根據 $S_t = \alpha Y_t + (1 - \alpha)*S_{t-1}$ 進行計算，對應到上述程式如以下：
| $(1 - \alpha)*S_{t-1}$ | $\alpha Y_t$ |
| -------------------------------------------------- | -------------------------------------- |
| `((avg->internal << avg->weight) - avg->internal)` | `(val << avg->factor)) >> avg->weight` |
注意：這邊換進去 internal 都進行 factor scaling
#### Linux 核心無線網路裝置驅動程式
針對 `linux/drivers/net/wireless` 去做探討。
EWMA 常被用於無線網絡驅動開發中，特別是用於信號強度的測量、網絡品質的評估，以及調整和優化網絡性能。
:::danger
巨集無法「呼叫」(call)，因其本質的操作是「展開」(expand)，注意用語。
:notes: jserv
> 收到！會注意的 [name=vestata]
:::
可以大量<s>調用</s> DECLARE_EWMA 巨集，找到位在 `include/linux/average.h` 中對 ewma 的定義。
- 其中有三個參數：
1. `name`：
2. `_precision`：這邊相當於上邊所訴 scaling factor
3. `_weight_rcp`：這邊相當於上面所訴的權重，$\alpha$
- 在這邊對於 name 使用 `##` token pasting。
- 例如，如果使用 `DECLARE_EWMA(avg_rssi, 10, 8)`，##name 會將 name 替換為 `avg_rssi`，從而生成 `ewma_avg_rssi`、`ewma_avg_rssi_init`、`ewma_avg_rssi_read` 和 `ewma_avg_rssi_add`，詳見 [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/@sysprog/c-preprocessor?type=view#%E9%96%8B%E7%99%BC%E7%89%A9%E4%BB%B6%E5%B0%8E%E5%90%91%E7%A8%8B%E5%BC%8F%E6%99%82%EF%BC%8C%E5%96%84%E7%94%A8%E5%89%8D%E7%BD%AE%E8%99%95%E7%90%86%E5%99%A8%E5%8F%AF%E5%A4%A7%E5%B9%85%E7%B0%A1%E5%8C%96%E9%96%8B%E7%99%BC)
- 可以在 `include/linux/average.h` 中看到 `ewma_##name##_add`， `ewma_##name##_read`中類似於剛剛提到的例題相同的操作。
:::danger
避免非必要的項目縮排 (即 `* ` 和 `- `)，以清晰、明確，且流暢的漢語書寫。
> 收到，未來會注意的！ [name=vestata]
:::
而在 `linux/drivers/net/wireless` 這個目錄中觀察到針對：`avg_rssi`, `beacon_rssi`, `rate`, `signal`等等進行 DECLARE_EWMA
- 針對 `ath11k/` 進行實際應用介紹
- 在 mac.c 中 `ath11k_mac_op_sta_statistics` 函數中，`ewma_avg_rssi_read` 被用來獲取當前的 EWMA 值。這個值反映了考慮到之前的 RSSI 測量後的平均信號強度，用於更新 sinfo 中的 signal_avg 。據接收到的數據包信息更新無線站點的統計和信號質量指標，其中包括實時更新 EWMA 計算的 RSSI 值，從而提供對無線信號質量的動態評估。
- 在 `dp_rx.c` 使用 `ewma_avg_rssi_add(&arsta->avg_rssi, ppdu_info->rssi_comb)` 更新 EWMA 平均值。這一步將當前的 RSSI 值加入到 EWMA 計算中 (arsta 為一個 ath10k_sta 結構體的變數，裡面存放各種無線連接訊息)
:::info
TODO
1. 嘗試更深入理解網路 `drivers/` 實際操作
:::
### 測驗五
#### 解釋程式碼運作原理
計算 $\lceil log_2(x) \rceil$，第一眼看這個程式碼真的是毫無頭緒。
```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;
}
```
先逐一分解程式：
1. `x--`：為了針對處理 x 本身是 2 的冪的清況，若不做此處理，最後一步 ceiling + 1 會導致推到下一個對數。
2. 由於是 `unsign integer 32 bit`，先查看 x 的最高為元是在前 16 位元還是後 16 位元。其中 `<< 4` 是代表如過 x 在高位元，我們要對 x 右移 16 位元。
- **可理解為將位移量存在 r 之中。**
```c
r = (x > 0xFFFF) << 4;
x >>= r;
```
3. 在這邊 shift 作為變量使 x 移動 shift 位元，在此處 r 改為**儲存位移總數**的變量。
```c
shift = (x > 0xFF) << 3;
x >>= shift;
r |= shift;
```
4. 同 2. 範圍在 0xF
5. 最後一步 `(r | shift | x > 1) + 1` 是多步驟寫在一起可以以下拆解：
- `r | shift`：程式進行到這等價於 `r |= shift`。
- `(r | shift | x > 1)`：最後做 `if (x > 1)` 的判斷，如果為真會加到 r 的位移總量。
- `+1`：取 ceiling。
#### 改進程式碼
使可以處理 `x = 0` ，並仍是 branchless 這個問題 $\equiv$ 不要使用 `x--;` 處理 2 的冪問題 $\equiv$
在這邊發現另一個問題：
| x | 0 | 1 | 2 | 3 | 4 | ... |
| ---------- | ---------------------------- | --------------------------- | --- | --- | --- | --- |
| $log_2(x)$ | <font color="#f00">32</font> | <font color="#f00">1</font> | 1 | 2 | 2 | ... |
所以有 `log0 = 32`, `log1 = 1` 共兩個問題。
1. 針對 `log0` 做修正
2.
> [commit 7d30243](https://github.com/vestata/linux2024-homework4/commit/7d30243e355fe648ff4f467e3b480b451e982218)
使用 bitwise 操作：
```diff
uint32_t r, shift;
- x--;
+ x -= !!x;
r = (x > 0xFFFF) << 4;
```
使用此方法 `log0 = 0`， `log1 = log2 = 1` 尚有錯誤。
#### Linux 核心原始程式碼
根據提示到 Linux 核心排程器 `kernel/sched/` 尋找：
## [第 4 周測驗題](https://hackmd.io/@sysprog/linux2024-quiz4)
### 測驗一
popcount 是計算數值的二進位表示中，有多少位元是 1。
- 版本一
使用的是 naive 手段，`v &= (v - 1)` 會在每一輪將位置最低的 1 清為 0。又每一次操作會有一個 n 作為計數，這邊使用 `n = -(~n)` $\equiv$ `n++` 實踐，是一個活用二補數系統的方法。詳細可以見 [第 4 周測驗題](https://hackmd.io/@sysprog/linux2024-quiz4) 。
- 版本二
改寫為 branchless 的手法
使用數學式：
$popcount(x) = x - \lfloor \frac{x}{2} \rfloor - \lfloor \frac{x}{4} \rfloor - ... - \lfloor \frac{x}{2^{31}} \rfloor$
以下皆為二進位去觀察：
令 $x = b_{31}...b_2b_1b_0$
:::info
TODO 完成 `__builtin_popcount` 的原理解析。
:::
hammind distance: 為二進位的每個位元的差，而 `a ^ b`，XOR 操作留下相異的位元，取其 popcount 便是 hamming distance.
考慮 LeetCode 477. Total Hamming Distance 這提的目標是求所有點之間的 hamming distance 之總和。
測驗題提供的程式碼：
```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 >> 1;
}
```
這是使用暴力法使用二層 for 迴圈計算所有 pair，所以每個 pair 會計算**兩次** hamming distance。所以最後一步再回傳質需要再除以二已得到正確答案。
此方法在 LeetCode 477 會 `Time Limit Exceeded`。
修正此暴力法：
```diff
- for (int i = 0;i < numsSize;i++)
+ for (int i = 0;i < numsSize - 1;i++)
- for (int j = 0; j < numsSize;j++)
+ for (int j = i+1; j < numsSize;j++)
total += __builtin_popcount(nums[i] ^ nums[j]);
- return total >> 1;
+ return total;
```
可以通過 LeetCode 477 但是時間表現在最後 20%，尚有進步空間。
找到其規律：
| | 4 | 3 | 2 | 1 | 0 |
| ------ | --- | --- | --- | --- | --- |
| 7 | 0 | 0 | 1 | 1 | 1 |
| 5 | 0 | 0 | 1 | 0 | 1 |
| 10 | 0 | 1 | 0 | 0 | 1 |
| 17 | 1 | 0 | 0 | 0 | 1 |
| result | 3 | 3 | 4 | 3 | 0 |
我們使用列的視角去觀看二進位表示。根據上面暴力法我們使用的 XOR 操作是針對每一位數有多少相異的位元。以上面的例子（依據上面列的標示）：
第 0 列有 4 個 1，其 XOR 結果也都會是 0，所以最後再計算 popcount 也會是 0。
第 1 列有一個 1 與 三個 0 ，在整個遍歷會出現 (1 ^ 0) 三次，所以總共的 popcount 次數會有 3 次。
第 2 列 有兩個 1 兩個 0，會分別有 ((1 ^ 0), (1 ^ 0)), ((1 ^ 0), (1 ^ 0))總共四次，所以在 popcount 也會增加 4 次。
以此類推...
同理我們可以每一列將它拆成：x 個 1 與 y 個 0，將 x * y 便是上面的結果（這是觀察的結果），也可以說是上面做法的歸納。
實作如以下：
```c
int totalHammingDistance(int* nums, int numsSize) {
int i, j, k, t;
t = 0;
for (i = 0; i < 32; i++) {
k = 0;
for (j = 0; j < numsSize; j++) {
k += (nums[j] & (1U << i)) ? 1 : 0;
}
t += k * (numsSize - k);
}
return t;
}
```
k 為 1 的計數，而整列不是 1 就是 0 所以使用 (numsSize - k) 作為0的數量。
在 leetcode 上測試使用 (1 << i) 會出現以下錯誤：
```shell
left shift of 1 by 31 places cannot be represented in type 'int'
```
原本 1 預設為 int 不能進行 << 31 操作，要使用 `1U` unsigned int 才可以。
但是而在本地電腦 `gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0` (1 << 31)可以正常編譯。也查看了 AddressSanitizer 也尚未發現問題。
:::info
TODO 為何會這樣？
:::
### 測驗二
目標：不使用任何除法就算出某數除以另一個數的餘數
\begin{align*}
2^k
\equiv
\begin{cases}
1 \pmod{3}, & \text{if } k \text{ is even} \\
-1 \pmod{3}, & \text{if } k \text{ is odd}
\end{cases}
\end{align*}
:::info
TODO 理解這段程式，真看不懂
:::
### 測驗三
考慮 XTree，XTree 的平衡機制與 AVL tree 相似，利用 hint 來評估是否需要做 rotate，然而 xt_node 的 hint 的計算方式是，其左右節點 hint 最大值 +1 並且只有在被呼叫到 xt_update 時才會被更新。
hint 怎麼去評估的？
近似而非精確：在 XTree 中，每個節點的提示值用於判斷樹的平衡狀態，但這個值並不需要與實際的最長子節點鏈長度完全一致。這樣可以減少在每次樹的修改操作後更新高度信息所需的計算量。
平衡操作的依據：當執行插入或刪除操作時，XTree 通過比較節點的提示值來決定是否需要進行旋轉來重新平衡樹。如果提示值顯示一側的鏈比另一側長得多，則可能需要進行平衡操作。
#### 程式碼解釋
##### treeint.c
`treeint_ops` 五種操作，再接上 `xt_ops` 對 `treein_xt` 進行操作。
`bench` 計算執行時間。
選擇 `xt_ops` 樹操作
通過 `ops->init` 初始化樹結構，並將其地址存儲在 `ctx` 中。
進行插入操作，根據種子是否為零使用線性或隨機方式生成元素值，測量並輸出每次插入操作的時間。
進行查找操作，方法同插入操作，測量並輸出每次查找操作的時間。
進行刪除操作，方法同插入和查找操作，測量並輸出每次刪除操作的時間。
最後，銷毀樹結構並結束程序。
> Additionally, if the node's hint becomes zero or experiences a change compared to its previous state during the update, modifications are made to the node's parent, as it existed before these update operations.
#### xtree.c
XTree 的操作基於四個基本的二元搜尋樹操作：rotate_left、rotate_right、replace_right、replace_left。
`xt_dir` ：指示方向（左、右、無）。
插入：按照二元搜尋樹的標準方法插入新節點，然後調用 `xt_update` 來保持或恢復平衡。
`xt_balance` 如果左子節點存在，則計算左子樹的高度（l），加上左子節點的 hint 屬性值加 1（hint 是用於存儲或表示節點高度或深度的字段）。
#### treeint_xt.c
如何將 XTree 整合為一個特定於**整數**的二元搜尋樹
Sign in with Wallet
Connect another wallet