# 2024 Homework4 (quiz3+4)
## 第 3 週測驗題
### isqrt1: 改寫第三版程式
```c
int i_sqrt(int x)
{
if (x <= 1) /* 假設 x 總是正數 */
return x;
int z = 0;
for (int m = 1UL << ((31 - __builtin_clz(x)) & ~1UL); m; m >>= 1) {
int b = z + m;
z >>= 1;
if (x >= b)
x -= b, z += m;
}
return z;
}
```
這段程式碼使用了一種稱為 "Digit-by-digit calculation" 的方法，來計算整數的平方根。基本上，它運用了二進位的特性，將要開平方的數拆成 2 的冪相加，然後進行運算，逐位計算結果。程式碼中的迴圈對應於這個逐位計算過程。
取代 GNU extension
如果我們要將 GNU extension 中的 __builtin_clz 替換為標準函式庫中的 ffs 或 fls，我們需要確保這兩個函式的功能和 __builtin_clz 一致。然後，我們只需要將程式碼中的 __builtin_clz(x) 替換為 ffs(x) - 1 即可。
### 測驗2
這段程式碼是用來計算兩個以字元陣列表示的正整數的加法，並將結果存儲在另一個字元陣列中。其中，每個字元代表一個位數，並以字符的形式表示 0 到 9 之間的數字。
程式碼運作原理
首先，將兩個正整數的對應位數相加，並加上之前的進位（carry）。
檢查相加後的結果是否超過 10。如果超過 10，則需要將進位設置為 1，否則為 0。
將結果中的每個位數都取模 10，並將其轉換為字符表示形式。
將結果存儲在結果陣列中。
調整成不依賴除法的程式碼
為了減少運算成本，這段程式碼使用了一種技巧來代替除法操作。這種技巧的核心思想是通過位運算來實現除法，進而實現 mod 10 和 div 10 的操作。
在這段程式碼中，利用了除法原理，將 mod 10 和 div 10 合併為一個操作。然後使用 bitwise operation 來實現除法。這裡的關鍵是找到一個適合的除數，並使用位運算來模擬除法運算。最後，將結果存儲在結果陣列中。
這種方法的優勢在於它減少了除法操作的使用，進而減少了運算成本。這對於嵌入式系統和對性能要求較高的應用場景特別有用。
### h2實作 % 9 和 % 5 程式碼
以下是分別計算 % 9 和 % 5 的程式碼：
```c
uint32_t mod_9(uint32_t num) {
return num - ((num >> 3) + (num & 0b111)); // num - (num / 9)
}
uint32_t mod_5(uint32_t num) {
return num - ((num >> 2) + (num & 0b11)); // num - (num / 5)
}
```
這兩個函式分別計算了給定數字的模 9 和模 5。它們都避免了使用除法操作，而是利用了位運算的特性來實現模運算。這樣可以更有效地計算模運算，同時減少運算成本。
### 測驗3
```c
static size_t ilog2(size_t i)
{
size_t result = 0;
while (i >= 65536) {
result += 16;
i >>= 16;
}
while (i >= 256) {
result += 8;
i >>= 8;
}
while (i >= 16) {
result += 4;
i >>= 4;
}
while (i >= 2) {
result += 1;
i >>= 1;
}
return result;
}
```
```c
int ilog32(uint32_t v)
{
return (31 - __builtin_clz(v));
}
```
程式碼運作原理
版本二:
此版本根據輸入的數值 i 的大小來選擇不同的迴圈進行。
首先檢查 i 是否大於等於 AAAA，如果是，則將 result 增加 16，並將 i 右移 16 位，以此類推，直到 i 小於 AAAA。
接著類似地檢查 i 是否大於等於 BBBB，CCCC，最後是 2，每次將 result 增加對應的位移數，並將 i 右移對應的位移數，直到 i 變為 0。
版本三:
此版本利用了 GNU extension __builtin_clz，該函式返回一個無符號整數的前導 0 的數量，即輸入的數值 v 在二進位表示中從最高位開始連續 0 的個數，並返回該值減去 31，即為對數的結果。
### 測驗4
程式碼運作原理
ewma_init():
此函式用於初始化 EWMA 結構的參數。
檢查 factor 和 weight 是否都是 2 的冪次方，如果不是，則產生斷言錯誤。
將 weight 和 factor 分別轉換為其對數值，使用 ilog2() 函式。
將 internal 初始化為 0。
ewma_add():
此函式用於將一個新的樣本值添加到 EWMA 中。
如果 internal 不為 0（即 EWMA 已經有過樣本），則使用指數遞減的方式更新 internal。這是通過將前一個值的一部分（internal << EEEE）減去前一個值（avg->internal），並加上新的值（val << FFFF），然後右移 weight 位來實現的。
如果 internal 為 0（即第一個樣本），則將 val 左移 factor 位，並將結果存儲在 internal 中。
ewma_read():
此函式用於讀取 EWMA 的平均值。
將 internal 右移 factor 位，然後返回結果。
### 測驗5
```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 > 0x1)) + 1;
}
```
程式碼運作原理
此程式碼實現了一個有效計算 ceil(log2(x)) 的方法，並將結果轉換為整數。以下是其運作原理：
將 x 減去 1，目的是將 x 轉換為 ceil(log2(x)) 中的上界數。
通過一系列右移操作來找到 ceil(log2(x)) 的值。首先，將 x 右移 4 位，然後將結果存儲在 r 中。接著，對 x 再進行右移和位運算，來尋找 log2(x) 的值，並將結果存儲在 shift 中。將 r 和 shift 進行位 OR 運算，得到 ceil(log2(x))。
最後，將 ceil(log2(x)) 加上 1，以得到 ceil(log2(x)) 的整數值。
### h2改進程式碼
若要處理 x = 0 的情況且仍然保持無分支，可以將原始 x 的值與 1 進行比較，如果 x = 0，則將 r 和 shift 都設置為 0。修改後的程式碼如下：
```c
int ceil_ilog2(uint32_t x)
{
uint32_t r = 0, shift = 0;
x = (x == 0) ? 0 : x - 1;
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 > 0x1)) + 1;
}
```
這樣修改後，即使 x 為 0，也不會引發任何分支。
## 第 4 週測驗題
### 測驗1
#### 程式碼運作原理
這段程式碼的主要思想是根據每個數字的每個位元，計算所有數字中該位元為 1 和為 0 的數量，並將兩者相乘後加總起來。這樣就可以得到所有數字之間的 Hamming distance。
具體步驟如下：
從最低位元 (LSB) 開始，遍歷每個位元。
對於每個位元，遍歷所有的數字，並統計該位元為 1 的數量。
將該位元為 1 的數量乘以該位元為 0 的數量，並將結果加到總和中。
重複以上步驟，直到遍歷完所有的位元。
返回總和，即為所有數字之間的 Hamming distance 總和。
#### 改進程式碼
要進一步改進程式碼，可以優化內部的迴圈結構以減少時間複雜度。一種可能的方法是使用單個循環計算每個位元為 1 的數量。以下是改進後的程式碼：
```c
int totalHammingDistance(int* nums, int numsSize)
{
int total = 0;
for (int i = 0; i < 32; i++) {
int countOnes = 0;
for (int j = 0; j < numsSize; j++) {
countOnes += (nums[j] >> i) & 1;
}
total += countOnes * (numsSize - countOnes);
}
return total;
}
```
這種方法在每次迭代中僅需進行一次內部迴圈，從而提高效率。
#### 不依賴 popcount，針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。
可以將數組 nums 的指針和其大小傳遞給這個函數，如下所示：
```c
#include <stdio.h>
int main() {
int nums1[] = {4, 14, 2};
int size1 = sizeof(nums1) / sizeof(nums1[0]);
printf("%d\n", totalHammingDistance(nums1, size1)); // 輸出: 6
int nums2[] = {4, 14, 4};
int size2 = sizeof(nums2) / sizeof(nums2[0]);
printf("%d\n", totalHammingDistance(nums2, size2)); // 輸出: 4
return 0;
}
```
這個實現不依賴內置的 popcount 函數，並提供了一個更有效的解決方案，用於計算漢明距離的總和。
### 測驗2
摘錄自《Hacker's Delight》:
#### 餘數除以數字的和法
要在沒有除法的情況下計算一個數除以另一個數的餘數，可以使用以下技巧。如果除數符合 $(2^k \pm 1)$，那麼可以使用以下方法來實現這個目的。
如果 $(a \equiv a' (\bmod b))$ 且 $(b \equiv b' (\bmod b))$，則 $(a + b \equiv a' + b' (\bmod b))$ 和 $(a - b \equiv a' - b' (\bmod b))$。
假設 $(a = ab_0 + a_1)$，$(b = bb_0 + b_1)$，$(a_1 \equiv a' (\bmod b))$ 和 $(b_1 \equiv b' (\bmod b))$，那麼 $(a + b \equiv a' + b' (\bmod b))$。接下來進行運算。
以除數為 3 為例，1 $equiv 1 (\bmod 3)$ 且 2 $equiv -1 (\bmod 3)$，將後者不斷的乘上前者可得
$2^k \equiv \begin{cases} 1 (\bmod 3), & \text{若} k \text{為偶數} \\ -1 (\bmod 3), & \text{若} k \text{為奇數} \end{cases}$
因此若 n 的二進位表示為 $(b_{31}b_{30} \dots b_1b_0)$，則
$n = \sum_{i=0}^{31} b_i \cdot 2^i$
由以上的推論可得
$n \equiv \sum_{i=0}^{31} b_i \cdot (-1)^{i} (\bmod 3)$。
將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為 $(n = \text{popcount}(n \& 0x55555555) - \text{popcount}(n \& 0xAAAAAAAA))$。
利用以下定理可以進一步化簡。
$\text{popcount}(n \& (n - 1)) - \text{popcount}(n) = \text{popcount}(n \oplus n) - \text{popcount}(n)$
於是 $(n = \text{popcount}(n \oplus 0xAAAAAAAA) - 16)$，將此式重複應用於得到的 n 上直到 n 介於 0~2，但為了避免 n 變成負數，我們要將它加上一個足夠大的 3 的倍數，文中的例子是加上 39。
範例程式如下:
```c
int mod3(unsigned n)
{
n = popcount(n ^ 0xAAAAAAAA) + 23;
n = popcount(n ^ 0x2A) - 3;
return n + ((n >> 31) & 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];
}
```
### 測驗3
這段程式碼實現了一種名為 XTree 的自平衡二元搜尋樹。它使用了二元搜尋樹的基本操作，如插入、刪除和查找，並且在查找操作中進行樹的平衡調整，從而實現了快速的插入和刪除操作。
XTree 通過四個基本的二元搜尋樹操作來實現平衡：rotate_left、rotate_right、replace_right 和 replace_left。其中，rotate_left 和 rotate_right 操作用於樹的平衡調整，而 replace_right 和 replace_left 則在刪除操作中使用，用於替換待刪除節點。
插入操作首先使用二元搜尋樹的插入方法將新節點插入到樹中，然後調用更新操作進行平衡調整。刪除操作則根據待刪除節點是否有左子節點和右子節點，分別進行不同的處理，並最終進行平衡調整。
Sign in with Wallet
Connect another wallet