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` 先取得[最高有效位](https://zh.wikipedia.org/zh-tw/%E6%9C%80%E9%AB%98%E6%9C%89%E6%95%88%E4%BD%8D)，目的是為了不超過 N 下，由大往小找到估計解，可以思考一下為什麼不是從小往大逼近 ? 其實很好理解當你由小往大去疊加你的 `result` 很容易會超過 N，所以比如說要找 $sqrt(56)$ 一定是先找到 $7*7<56$ 再找 $2*2<56-49$，不過這是 10 進位的逼近，二進位一定會有較大誤差，因為依照這個方法其實不會先找到 7~10~ = 0111~2~ 而是會先找到 4~10~ = 100~2~，所以最終估計出來的只能到 (111~2~)^2^ = 49~10~。
* 版本二 : 不使用 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*\tfrac{a}{2^N} \simeq \tfrac{tmp}{10}$ ，那這裡會好奇原本的除以 10 不能依照這個先乘以倍數在除以 2 的冪嗎 ? 答案是不行因為 2^N^ 本身**不具有 5 的因數**所以不管怎麼除都不會是 $10 \not=\tfrac{2^N}{a}$。

所以這時需要另外找 10 以外的 $x$ 來證明什麼時候能滿足精度的要求。

證明可參考[講義](https://hackmd.io/@sysprog/linux2024-quiz3#%E6%B8%AC%E9%A9%97-2)，推導結果 (1) $9.55 \le x \le 10$，因此只要找到$x=\tfrac{2^N}{a}$滿足條件 (1) 的 2 的冪和 a。因此當 $a=13,N=7$ 可以滿足條件。

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

回到剛剛的除法替代 $tmp*\tfrac{a}{2^N}=tmp * \tfrac{13}{128} = tmp * \tfrac{2^0+2^2+2^3}{2^7}$ 到這裡還能明白但不知為何需要先將 $13 * tmp$ 除以 8 在乘回來(待釐清)，目前是認為因為商的結果都會處在較高位，如果一開始就用左移操作，且原本儲存在 bits 就不是很大就有機會吃掉商的值，為了盡可能避免這狀況發生，所以先除後乘法返還。
#### 第三題
目標 : 實作 log~2~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](https://en.wikipedia.org/wiki/Moving_average#Exponential_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` 假設為$\bar\alpha$，$\bar\alpha \alpha=1$， $\bar\alpha S_t=\bar\alpha\alpha Y_t+\bar\alpha(1-\alpha) S_{t-1}=>\bar\alpha S_t= Y_t+\bar\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)
#### 第三題