2024q1 Homework4 (quiz3+4)

contributed by < Wufangni >

第三週測驗

測驗 1

i_sqrt 為找出平方根的函式，下面為版本一的作法:

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

使用 log2 找出最高位元數 msb ，接著利用 if ((result + a) * (result + a) <= N) 判別本次迴圈的結果取平方是否小於原數，若不是則持續往下找，直到找出平方可小於原數的結果即為他的平方根。
版本二使用迴圈方式替代 log2 函式找出最高位元 msb:

int i_sqrt(int N)
{
    int msb = 0;
    int n = N;
    while (n > 1) {
        n >>= 1;
        msb++;
    }
    int a = 1 << msb;
    int result = 0;
    while (a != 0) {
        if ((result + a) * (result + a) <= N)
            result += a;
        a >>= 1;
    }
    return result;
}

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

測驗 2

carry = tmp / 10;
tmp = tmp % 10;

因 mod 的計算量較大，根據除法原理利用已計算出來的 tmp / 10 可將 % 改寫成下面形式:

carry = tmp / 10;
tmp = tmp - carry * 10;

接著著手改寫 divmod_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));   
}

(in | 1) - (in >> 2) 可看成

$in-(\frac{in}{4})$ ，化簡開可得

$0.75in$，因此 q 的計算結果為

$\frac{3}{4}in\cdot \frac{1}{16}+\frac{3}{4}in$， 再整理後可得

$\frac{102}{128}in$，做了四次 q = (q >> 8) + x; 讓 q 的結果更趨近於

$0.8in$ ， 最後可計算 div 結果，

$\frac{8}{10}in\cdot \frac{1}{8}=\frac{1}{10}in$。

mod 計算則利用 (q & ~0x7) 方式，將 ~0x7 看待成 0x11...1000 與 q 做 & 計算，相等於 div 乘上

$8$ ，再與 (*div << 1) 相加可得結果為

$div\cdot 8+div\cdot 2=div\cdot 10$，根據上述提到的 mod 簡化算法 tmp = tmp - carry * 10 代入數值，mod 即為

$in-div\cdot 10$ 結果。

測驗 3

定義一個 ilog2 用來找出以 2 為底的對數，每次迴圈中 i 的二進位值都會右移一格，用 log 作為計數器計算有幾個

$2^n,n\ge 0$ 。

int ilog2(int i)
{
    int log = -1;
    while (i) {
        i >>= 1;
        log++;
    }
    return log;
}

上述方法因每個 bit 都需掃過一次做計算，因此改良成下面版本，在迴圈中新增判別式判斷 i 是否大於某個

$2^n,n\ge 0$ ，若達成條件則一次移動 n 格 bit ，以減少總迴圈次數。

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

使用 GNU 中提供的 __builtin_clz ，因輸入不能為零所以設置 v | 1 作為輸入。

int ilog32(uint32_t v)
{
    return (31 - __builtin_clz(v | 1));
}

測驗 4

預先定義 ewma 結構， internal 為當前 ewma 的值， factor 為縮放因子，weight 用來決定衰減的

$\alpha$ 大小。

struct ewma {
    unsigned long internal;
    unsigned long factor;
    unsigned long weight;
};

初始化 ewma 結構體，因 factor 及 weight 必須為 2 的冪，使用 is_power_of_2 排除可能報錯的值，接著使用測驗 3 提及的 ilog2 取出 2 的次方。

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_add 更新 ewma ，添加新資料 val ，若 avg->internal 為空值代表 val 為

$Y_0$，直接填入 val << avg->factor ，其餘情況則按照

$\alpha Y_t+(1-\alpha )\cdot S_{t-1}$ 更新

$S_t$。

$\alpha$ 以

$\frac{1}{2^{avg->weight}}$ 表示，

$\alpha Y_t$ 則可以以 (val << avg->factor)) >> avg->weight 實現。

$(1-\alpha )$ 可寫成

$\frac{2^{avg->weight}-1}{2^{avg->weight}}$，乘回 avg->internal 展開可得

$[(2^{avg->weight})(avg\to internal)-(avg\to internal)]/2^{avg->weight}$，前半部分可以 ((avg->internal << avg->weight) - avg->internal) 實現，最後因 (val << avg->factor)) >> avg->weight 也需 >> avg->weight 因此將此移至算式尾端當分母。

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

第四周測驗題

測驗 1

計算數值的二進位表示法中有被設置的 bit 數量， popcount_naive 為其中一種方式:

unsigned popcount_naive(unsigned v)
{
    unsigned n = 0;
    while (v)
        v &= (v - 1), n = -(~n);
    return n;
}

利用 v &= (v - 1) 重置數值中 LSB 位元，並使用 n = -(~n) 方式對 n 加一，直到所有 LSB 位元重置為止。

以另一種方式做改寫:

unsigned popcount_branchless(unsigned v)
{
    unsigned n;
    n = (v >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;
    n = (n >> 1) & 0x77777777;
    v -= n;

    v = (v + (v >> 4)) & 0x0F0F0F0F;
    v *= 0x01010101;                                     

    return v >> 24;
}

以 32bit 舉例，population count 可以下列數學式表示:

$popcount(x)=x-\lfloor \frac{x}{2}\rfloor -\lfloor \frac{x}{4}\rfloor -...-\lfloor \frac{x}{32}\rfloor$
為了避免每個 bit 都做一次計算，可以以每 4 個 bit 同時做計算，即:

$popcount(x)=x-\lfloor \frac{x}{2}\rfloor -\lfloor \frac{x}{4}\rfloor -\lfloor \frac{x}{8}\rfloor$
n = (v >> 1) & 0x77777777 得出

$\lfloor \frac{x}{2}\rfloor$，持續累加三次得到以 4 bits 為單位的 set bit 數量。

v = (v + (v >> 4)) & 0x0F0F0F0F;
v *= 0x01010101; 
return v >> 24;

利用一次位移一個 4 bits 單位做相加乘上 0x0F0F0F0F 過濾多餘的內容，可得以下數列，

$Bn$ 為第 n 個單位 set bit 數量。

0 (B7+B6) 0 (B5+B4) 0 (B3+B2) 0 (B1+B0)

最後乘上 0x01010101 並取出在原 A6 位置的結果 (B7+B6+B5+B4+B3+B2+B1+B0)，即為總 set bit 數目。

int hammingDistance(int x, int y)
{
    return __builtin_popcount(x ^ y);
}

Hamming distance 為兩數列不相同位元之數目，透過 GCC 內建函式庫中提供 __builtin_popcount(x) 可計算 set bit 數量，可利用

$XOR$ 特性(相同為0，不同為1)計算

$A\oplus B$ ，得出數列 A 與數列 B 相異位元的數列，即為 A ^ B。

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

測驗 3

從 xtree.h 中先觀察 xt_node 結構:

struct xt_node {
    short hint;
    struct xt_node *parent;
    struct xt_node *left, *right;
};

*parent 作為指向父節點的指標，*left 及 *right 分別指向左右子樹的根節點，hint 則作為判斷是否處於平衡的變數。
利用 treeint_xt.c 中提供對 xt_tree 的基本操作，完成 __xt_remove 及 xt_insert 等節點操作。

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