contributed by <stevendd543>

第 3 週測驗題

第一題

目標 : 以二進位操作完成 square root 的逼近值

• 版本一 : 使用 log2 完成

#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(N)<<1 先取得最高有效位，目的是為了不超過 N 下，由大往小找到估計解，可以思考一下為什麼不是從小往大逼近 ? 其實很好理解當你由小往大去疊加你的 result 很容易會超過 N，所以比如說要找

$sqrt(56)$ 一定是先找到

$7\ast 7<56$ 再找

$2\ast 2<56-49$，不過這是 10 進位的逼近，二進位一定會有較大誤差，因為依照這個方法其實不會先找到 7₁₀ = 0111₂ 而是會先找到 4₁₀ = 100₂，所以最終估計出來的只能到 (111₂)² = 49₁₀。

• 版本二 : 不使用 log2 完成

    while (n > 1) {
        n >>= 1;
        msb++;
    }

其實原本的 log2 只是要用來取得 msb 所以可以不必使用 log2 也能完成。

• 版本三

第二題

static void str_add(char *b, char *a, char *res, size_t size)
{
    int carry = 0;

    for (int i = 0; i < size; i++) {
        int tmp = (b[i] - '0') + (a[i] - '0') + carry;
        carry = tmp / 10;
        tmp = tmp % 10;
        res[i] = tmp + '0';
    }
}

這段程式碼本身在作字串數字相加，但目標為了提高效率將其除法與乘法替換成 bitwise operation，當然精度肯定會減少，但我們只求小數點後第一位是精準即可，因此才有機會使用 bitwise operation 操作。

首先需要思考的事情是除以10並不能用 2 的冪表示，換句話說不能以右移來代替除法，因此需要數學證明除數，除了 10 外在什麼樣的範圍內可接受且滿足精度在小數點後一位是精準的。

我先講結論，最後可以透過先將 tmp 乘以一個倍數 a ，再除以一個 2 的冪 來代替除法，以數學公式表示

$tmp\ast \frac{a}{2^N}\simeq \frac{tmp}{10}$ ，那這裡會好奇原本的除以 10 不能依照這個先乘以倍數在除以 2 的冪嗎 ? 答案是不行因為 2^N 本身不具有 5 的因數所以不管怎麼除都不會是

$10\ne \frac{2^N}{a}$。

所以這時需要另外找 10 以外的

$x$ 來證明什麼時候能滿足精度的要求。

證明可參考講義，推導結果 (1)

$9.55\le x\le 10$，因此只要找到

$x=\frac{2^N}{a}$滿足條件 (1) 的 2 的冪和 a。因此當

$a=13,N=7$ 可以滿足條件。

    q = (((tmp >> 3) + (tmp >> 1) + tmp) << 3) >> 7;                         

回到剛剛的除法替代

$tmp\ast \frac{a}{2^N}=tmp\ast \frac{13}{128}=tmp\ast \frac{2^0+2^2+2^3}{2^7}$ 到這裡還能明白但不知為何需要先將

$13\ast tmp$ 除以 8 在乘回來(待釐清)，目前是認為因為商的結果都會處在較高位，如果一開始就用左移操作，且原本儲存在 bits 就不是很大就有機會吃掉商的值，為了盡可能避免這狀況發生，所以先除後乘法返還。

第三題

目標 : 實作 log₂x 的二進位求值
版本一 : 透過右移算子向下取整求出整數對數

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

假設

$2^x\le i<2^{x+1},x\in N$， ilog2 將會向下取整輸出

$x$。

版本二 : 透過二分搜尋法減少計算量

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

版本三 : 換句話說其實只要找到最高有效位的 bit 就是答案了，因此可以使用31 - __builtin_clz() 來完成。

第四題

Exponential Weight Moving Average

• What is moving average : 那就如字面上的意思，滾動式地計算平均，有方法是固定取 k 個時間點取平均，稱之為 simple moving average，如果有接觸股市就可知道，N 日均線就是一種 SMA。也有方法是採用累加的方式來計算平均，就像 Cumulative average 每當有新資料，就將原本的平均展開並加上新資料來取平均。那 Exponential Weight Moving Average 與這些差異在於，多了權重的參與，讓當下的資料與過去所有資料的平均有權重上之分，這裡的 Exponential 就是過去的資料重要性會隨著越舊而指數下降。

原理:

It maintains a structure housing the EWMA parameters alongside a scaled internal representation of the average value, aimed at minimizing rounding errors.

可以看到程式碼中提到，使用了 structure 儲存 EWMA 參數，其中參數包含了 factor、weight、internal，(1) 這裡的 factor 強調是為了 minimizing rounding errors 也就是定點數的 scaling factor ，(2) 而 weight 則是以 2 的冪來表示，但要注意這裡的 weight 並不是

$\alpha =2^{-n}$ ， 而是透過 log 取得

$weight=n$，這是為了 bitwise operation 而儲存的形式，因此就可以透過右移 weight 個 bits 來達到乘以 2^-n 操作。(3) 最後 internal 全名為 internal representation 簡單翻譯就是內部表達式，換句話說因為這是定點數操作，所以當你乘上 factor 轉換成定點數後，這些平均結果都會以內部表示式來呈現，也就是定點數的呈現方式，當你要透過 unsigned long ewma_read(const struct ewma *avg) 讀取真正的值才會利用 左移 factor 個 bits 來返還真實值。

特別注意到 ewma_add 這個計算 EWMA 的函式，因為我們知道 EWMA 公式為

$S_t=\alpha Y_t+(1-\alpha )S_{t-1}$，先將其乘以權重 avg->weight 假設為

$\overline{\alpha }$，

$\overline{\alpha }\alpha =1$，

$\overline{\alpha }{S}_t=\overline{\alpha }\alpha Y_t+\overline{\alpha }(1-\alpha )S_{t-1}=>\overline{\alpha }{S}_t=Y_t+\overline{\alpha }{S}_{t-1}-S_{t-1}$ 最後再把結果 >>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;
}

第五題

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

這段程式碼跟測驗三同樣使用的是二分搜尋法，只是以不同方式表達，
while (i >= 65536) 對應到 r = (x > 0xFFFF) << 4 這裡不用 while 的原因是輸入只有 32bits，不會重複執行。result += 16 對應到 r |= shift ，然後 i >>= 16 對應到 x >>= shift。

延伸問題

如果 x=0 ，在第一步就會發生向下溢位，出來的結果就會不正確，因此要確保再 x 等於 0 的時候不作減法x += !!x，不過這個在沒有明確定義輸入錯誤的處理，只能避免溢位，答案仍然會是錯誤的。如果可接受溢位，也可在 x-- 後添加 x += (x > (x+1))。
額外提及一點還有 x 型態為 uint32_t ，因此 x > 0xFFFF 並不會發生，因此此條件永遠不會成立，不過如果考量到通用性，確實可以將其程式碼保留。

第 4 週測驗題

第一題

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

計算每對

$HammingDistance(nums[i],nums[j])$，但因為每一對都會出現兩次因此最後要除以 2。

第二題

​​​​n = popcount(n & 0x55555555) - popcount(n & 0xAAAAAAAA)

第三題