2024q1 Homework4 (quiz3+4)

contributed by < ollieni >

quiz3

測驗一 : 平方根

版本一的程式是先對要找平方根的整數 N 取對數(以二為底)，可以找出 msb (most significant bit) ，也就是用二進位表示這個整數時，最高位1是在從右開始數的第幾位。
有了 msb 後，因為整數 N 的平方根不可能超過 msb ，所以將 1 左移 msb 個位元後放入 a，接下來就可以開始用 while 迭代，在每一次迭代中，它會檢查 (result + a) * (result + a) 是否小於或等於 N。如果是，則將 result 加上 a，然後將 a 右移(除以二)，迭代完就可以逼近整數平方根。

版本二就是不直接使用取對數的方法，用將 N 右移的方式，右移幾次 N 不大於 1，次數就是 msb，接下來就和版本一一樣了。

版本三

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

bit 的翻譯是「位元」，而非「位」，後者是量詞。

__builtin_clz(x) 函式返回 x 的二進制表示中從最高位到最低位第一個非零位前的零的個數。
這個版本用__builtin_clz(x) 函式找出 msb 。
((31 - __builtin_clz(x)) & ~1UL) ，用 31 減去 零的個數後 ，可以得到 msb ， & ~1UL 把最後一位轉成 0 ，是因為每次 m 右移兩位，要強制對齊成偶數。

測驗二 : 針對正整數在相鄰敘述進行 mod 10 和 div 10 操作，如何減少運算成本？

我覺得重點是 "mod 10 就是 tmp 減去 div 10 的結果乘 10"。

#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 >> 3);
    *mod = in - ((q & ~0x7) + (*div << 1));   
}

uint32_t x = (in | 1) - (in >> 2); 這行就等於，in最後一位強制為1 - (in/4)，約等於

$x={\displaystyle \frac{3}{4}}\times in$ 。
uint32_t q = (x >> 4) + x;，這一行程式等同於

$q={\displaystyle \frac{3}{4}}\times in+{\displaystyle \frac{3}{64}}\times in={\displaystyle \frac{51}{64}}\times in\approx 0.79\times in$。
接下來這幾行是為了讓 q 接近

${\displaystyle \frac{8}{10}}\times in$，加了四次

${\displaystyle \frac{1}{256}}\times 0.79\times in$。

    x = q;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;
    q = (q >> 8) + x;

最後 *div = (q >> 3); 右移3位，等於除8，就變成

${\displaystyle \frac{1}{10}}\times in$。
而 *mod 就等於 in - ((q & ~0x7) + (*div << 1)); ，in - 商數乘10。

測驗三 : 考慮 ilog2 可計算以 2 為底的對數，且其輸入和輸出皆為整數

版本一是將要取對數的樹一直右移，並計算右移的次數，以此找出 msb，要從 -1 開始加是因為 log1 = 0。

版本二則是檢查要取對數的值大於65535、256、16、2時，可以一次右移16、8、4、1個 bits。

版本三是使用測驗一有提到的 __builtin_clz(x) 找出最高位到最低位第一個非零位前的零的個數，並用 31 減去即可得到以二為底的對數。

測驗四 : EWMA

Chatgpt 對於 EWMA 的解釋如下 : > EWMA 是指指數加權移動平均。它是一種統計方法，用於分析數據點，將較近期的數據賦予更高的權重，而對較舊的數據賦予較低的權重。在 EWMA 中，每個數據點都以指數方式加權，隨著數據點越來越遠，權重呈指數衰減。這種方法特別適用於金融分析、信號處理和質量控制等領域，其中近期的數據點通常比舊的更具決策價值。EWMA 常用於平滑噪聲數據、檢測趨勢以及識別時間序列中的異常或變化。

閱讀權威材料。

 * ewma_add() - Exponentially weighted moving average (EWMA)
 * @avg: Average structure
 * @val: Current value
 *
 * Add a sample to the average.
 */
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;
}

根據題目

$S_t=\{\begin{array}{ll}{Y}_0,& t=0\\ \alpha Y_t+(1-\alpha )\cdot S_{t-1},& t>0\end{array}$
題目中的三元條件運算式就是這個數學式。

也就是說在 avg->internal 是 0 的情況下，avg->internel = (val << avg->factor)。
對於為什麼要左移 factor bits，我問 Chatgpt後，有了以下的解釋 :

factor 是用於縮放內部值的因子。這個因子的作用是調整內部值的大小，以便在內部表示中容納指定範圍內的數值。

具體來說，factor 用於計算加權平均的內部表示，這涉及將實際值（例如計數或度量）轉換為內部表示。通常，為了在 EWMA 中處理大範圍的數值，需要將這些值進行縮放，以確保它們可以被有效地處理。因此，factor 就是用於進行這種縮放的參數。

而 avg->internal 不是 0 的情況下，(((avg->internal << avg->weight) - avg->internal) + (val << avg->factor)) >> avg->weight，最後為什麼要右移 avg->weight 還不太明白。

測驗五 : 計算

$\lceil {\log }_{2}x\rceil$

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

前面的步驟都是和測驗三找對數時一樣的概念，重點在最後的回傳值，return (r | shift | x > 1) + 1;將 shift 和 x > 1 (如果 x 大於1，則為1，否則為0) 添加到 r 中，並將結果加1返回。這是因為在一開始計算2的冪前，我們將 x 減1，所以最終結果需要再加1。

quiz4

測驗一 : popcount

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

這段程式將 nums 裡的數，透過兩個 for 迴圈遍歷交叉使用__builtin_popcount(nums[i] ^ nums[j]) 計算，(nums[i] ^ nums[j]) 有幾個1，就可以得知在二進制時，每個位元的差。
最後右移 1 bits 的原因是因為會重複計算，比如 i = 1, j = 2 和 i = 2, j = 1 重複了，所以最後結果要除以2。

測驗二 : Remainder by Summing digits

測驗三 : Xtree

這題針對 static void __xt_remove(struct xt_node **root, struct xt_node *del) 這個函式作解釋。

static void __xt_remove(struct xt_node **root, struct xt_node *del)
{
    if (xt_right(del)) {
        struct xt_node *least = xt_first(xt_right(del));
        if (del == *root)
            *root = least;

        xt_replace_right(del, least);
        xt_update(root, xt_right(least));
        return;
    }

    if (xt_left(del)) {
        struct xt_node *most = xt_last(xt_left(del));
        if (del == *root)
            *root = most;

        xt_replace_left(del, most);
        xt_update(root, xt_left(most));
        return;
    }

    if (del == *root) {
        *root = 0;
        return;
    }

    /* empty node */
    struct xt_node *parent = xt_parent(del);

    if (xt_left(parent) == del)
        xt_left(parent) = 0;
    else
        xt_right(parent) = 0;

    xt_update(root, parent);
}

首先，檢查待刪除節點 del 是否有右子節點(xt_right(del))。

如果有右子節點，找到右子樹中的最小節點 least，並將其設為待刪除節點 del 的右子節點。
如果 del 為根節點，則更新根節點為 least。
然後，使用 xt_update 更新根節點，以確保樹的平衡性。
如果待刪除節點 del 沒有右子節點，則檢查它是否有左子節點(xt_left(del))。

如果有左子節點，找到左子樹中的最大節點 most，並將其設為待刪除節點 del 的左子節點。
如果 del 為根節點，則更新根節點為 most。
然後，使用 xt_update 更新根節點，以確保樹的平衡性。