2024 Homework4 (quiz3+4)

第 3 週測驗題

isqrt1: 改寫第三版程式

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 的程式碼：

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

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

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

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。修改後的程式碼如下：

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 的數量。以下是改進後的程式碼：

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 的指針和其大小傳遞給這個函數，如下所示：

#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^{'} (mod b))

且

(b \equiv b^{'} (mod b))

，則

(a + b \equiv a^{'} + b^{'} (mod b))

和

(a - b \equiv a^{'} - b^{'} (mod b))

。

假設

(a = a b_{0} + a_{1})

，

(b = b b_{0} + b_{1})

，

(a_{1} \equiv a^{'} (mod b))

和

(b_{1} \equiv b^{'} (mod b))

，那麼

(a + b \equiv a^{'} + b^{'} (mod b))

。接下來進行運算。

以除數為 3 為例，1

e q u i v 1 (mod 3)

且 2

e q u i v - 1 (mod 3)

，將後者不斷的乘上前者可得

2^{k} \equiv {\begin{cases} 1 (mod 3), & 若 k 為偶數 \\ - 1 (mod 3), & 若 k 為奇數 \end{cases}

因此若 n 的二進位表示為

(b_{31} b_{30} \dots b_{1} b_{0})

，則

n = \sum_{i = 0}^{31} b_{i} \cdot 2^{i}

由以上的推論可得

n \equiv \sum_{i = 0}^{31} b_{i} \cdot (- 1)^{i} (mod 3)

。

將每次得到的位元和遞迴的應用上式直到得到一個小於 3 的數即是餘數，若變成負數則要加上 3 的倍數。位元和通常又可以利用 population count 這類的函式來得到，因此寫成程式的話可以將上式表示為

(n = popcount (n & 0 x 55555555) - popcount (n & 0 x A A A A A A A A))

。

利用以下定理可以進一步化簡。

popcount (n & (n - 1)) - popcount (n) = popcount (n \oplus n) - popcount (n)

於是

(n = popcount (n \oplus 0 x A A A A A A A A) - 16)

，將此式重複應用於得到的 n 上直到 n 介於 0~2，但為了避免 n 變成負數，我們要將它加上一個足夠大的 3 的倍數，文中的例子是加上 39。

範例程式如下:

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

另一種變形是利用 lookup table 。

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 則在刪除操作中使用，用於替換待刪除節點。

插入操作首先使用二元搜尋樹的插入方法將新節點插入到樹中，然後調用更新操作進行平衡調整。刪除操作則根據待刪除節點是否有左子節點和右子節點，分別進行不同的處理，並最終進行平衡調整。

2024 Homework4 (quiz3+4)

第 3 週測驗題

isqrt1: 改寫第三版程式

測驗2

h2實作 % 9 和 % 5 程式碼

測驗3

測驗4

測驗5

h2改進程式碼

第 4 週測驗題

測驗1

程式碼運作原理

改進程式碼

不依賴 popcount，針對 LeetCode 477. Total Hamming Distance 撰寫出更高效的程式碼。

測驗2

餘數除以數字的和法

測驗3

Read more

2024q1 Homework5 (assessment)

2024q1 Homework6 (integration)

2024q1 Homework1 (lab0)

2024q1 Homework2 (quiz1+2)