# 2023q1 Homework2 (quiz2)

## 測驗 1

先將原本的程式碼改寫成比較簡短的形式

uint64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}

不過發現題目與原本考試的時候應該不相同，因為改寫過後的程式無法符合目前題目的敘述。現在題目的敘述為求出大於等於 2 的冪，但上面的程式只符合求出大於 2 的冪。於是改寫程式碼，如果將 `x` 先扣掉 1 ，再進行原本補全下方 0 的方法，就可以求得我們想要的結果。但是有一個例外是當 `x` 等於 0 的時候，輸出結果為 0 ，而不是 $2^0$ ，所以需要用一個判斷式去特判 0 的情況。

uint64_t next_pow2(uint64_t x)
{
    if(x == 0)
        return 1;
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    x |= x >> 32;
    return x + 1;
}

再來我們使用 `__builtin_clzl` 進行改寫，只要用 1 去向左推移 leading 0-bit 的數量，就可以得到我們要的答案。

uint64_t next_pow2(uint64_t x)
{
    if(x == 0)
        return 1;
    return 1 << (64 - __builtin_clzl(x));
}

因為在 [6.59 Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 中有寫到，若 `x` 等於則結果會是 undefined ，所以依舊需要特判掉 0 這個輸入。

> Built-in Function: int __builtin_clzl (unsigned long)
Similar to __builtin_clz, except the argument type is unsigned long.

> Built-in Function: int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.

而在編譯之後可以從 assembly code 中找到


## 測驗 2

int concatenatedBinary(int n)
{
    const int M = 1e9 + 7;
    int len = 0; /* the bit length to be shifted */
    /* use long here as it potentially could overflow for int */
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        /* removing the rightmost set bit
         * e.g. 100100 -> 100000
         *      000001 -> 000000
         *      000000 -> 000000
         * after removal, if it is 0, then it means it is power of 2
         * as all power of 2 only contains 1 set bit
         * if it is power of 2, we increase the bit length
         */
        if (!((i - 1) & i))
            len++;
        ans = (i | (ans << len)) % M;
    }
    return ans;
}

考慮到以下的性質
1. 在 `1 <= i <= n` 的情況下，當 `i` 為 2 的冪時，二進位的位數會比 `i-1` 還要多一位。
2. 當`i` 減 1 時，會把二進位表示中最低位的 1 變成 0 ，並把這個 1 之後的所有位元全部變成 1 。

這樣我們就可以開始解釋程式碼
- `len` 表示 `i` 的二進位位元長度。
- `ans` 用來儲存結果。
- 迴圈會遍歷 1 ~ n 。
- `if` 用來判斷 `i` 是否為 2 的冪，方法如下：
- 如果將 `i & (i - 1)` ，我們就會捨棄掉 `i` 二進位表示中最低位的 1 (性質 2)。
- 若是 `i` 為 2 的冪，則 `i & (i - 1)` 會等於 0 ，其餘則為 1 。
- 若是 `i` 為 2 的冪，代表 `len` 需要加 1 (性質 1)。
- 將 `ans` 推移 `len` 之後與 `i` 進行 bitwise OR ，目的是把 `i` 加到 `ans` 中。

### 改進模運算

因為完全沒想法，我就去問 chatgpt 要怎麼加速模運算，它跟我說可以使用 Barrett reduction 。修改後的程式碼如下。

int concatenatedBinary(int n)
{
    const unsigned int M = 1e9 + 7;
    int len = 0;
    const int k = 30;
    unsigned int mu = (1ul << (2*k)) / (double) M;
    long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (!((i - 1)&i))
            len++;
        ans = (i | (ans << len));
        unsigned long tmp = ((ans >> (k-1)) * mu) >> (k+1);
        ans = ans - tmp * M;
        if(ans >= M)
            ans -= M;
    }
    return ans;
}

這個算法首先會先選擇一個合適的基底 $b$ ，而通常會是 2 的冪，因為這樣不論是乘法或是除法運算都可以使用 bitwise shift 來進行操作。 $b$ 用來計算 $\mu = \lfloor \frac{b^{2k}}{M} \rfloor$ ,而 $k = \lfloor log_b M \rfloor + 1$ 。我們先假設 $0 \leq x < b^{2k}$ ，並且令 $q = \lfloor \frac{x}{M} \rfloor$ ， $r = x mod M = z - qM$ 。
首先因為 $\frac{x}{p} = \frac{x}{b^{k-1}} \frac{b^{2k}}{M} \frac{1}{b^{k+1}}$ (分子分母都同乘 $b^{2k}$ 只是分母部份分成兩個數字)，加入下高斯符號後可以得到不等式 $0 \leq \hat{q} = \lfloor \frac{\lfloor \frac{x}{b^{k-1}} \rfloor \mu}{b^{k+1}} \rfloor \leq \lfloor \frac{x}{M} \rfloor = q$ 。
再來，我們令 $\alpha = \frac{x}{b^{k-1}} - \lfloor \frac{x}{b^{k-1}} \rfloor$ ， $\beta = \frac{b^{2k}}{M} - \lfloor \frac{b^{2k}}{M} \rfloor$ ，而依照下高斯的性質 $0 \leq \alpha, \beta < 1$ 。把 $\alpha, \beta$ 帶入 $q$ 。

$q = \lfloor \frac{(\lfloor \frac{x}{b^{k-1}} \rfloor + \alpha)(\lfloor \frac{b^{2k}}{M} \rfloor + \beta)}{b^{k+1}} \rfloor$

若是把上式乘開，並假設 $\alpha = \beta = 1$ ，可以得到

$q < \lfloor \frac{\lfloor \frac{x}{b^{k-1}} \rfloor \mu}{b^{k+1}} + \frac{\lfloor \frac{x}{b^{k-1}} \rfloor + \lfloor \frac{b^{2k}}{M} \rfloor + 1}{b^{k+1}} \rfloor$

此時，我們假設 $0 \leq x < b^{2k}$ (我覺的這邊很像硬湊數字去滿足我們想要的結果)以及 $b^{k-1} \leq p < b^k$ ，用這兩個不等式可以得到

$\lfloor \frac{x}{b^{k-1}} \rfloor \leq b^{k+1}-1$
$\lfloor \frac{b^{2k}}{M} \rfloor \leq b^{k+1}$

再來把這兩個不等式帶入 $q$ 的不等式當中

$q < \lfloor \frac{\lfloor \frac{x}{b^{k-1}} \rfloor \mu}{b^{k+1}} + \frac{\lfloor \frac{x}{b^{k-1}} \rfloor + \lfloor \frac{b^{2k}}{M} \rfloor + 1}{b^{k+1}} \rfloor \leq \lfloor \frac{\lfloor \frac{x}{b^{k-1}} \rfloor \mu}{b^{k+1}} + 2 \rfloor = \hat{q} + 2$

我們就可以得到 $\hat{q} \leq q < \hat{q} + 2 \rightarrow q \geq \hat{q} > q - 2$ 。帶回 $r = x - qM$ ，就可以得到 $r \leq \hat{r} < r + 2M$ ，所以我們使用 $\hat{q}$ 求出的 $\hat{r}$ 最多只需要在扣掉一次 $M$ 就會是答案。

回到我們的程式碼，基底 $b = 2$ ，而 $k = \lfloor log_2{1000000007} \rfloor + 1 = 30$ ，只要我們事先計算好 $\mu = \lfloor \frac{b^{2k}}{M} \rfloor$ ，那每次進行模運算，就只需要 2 個 bitwise shift 和 1 個乘法就可以取得 $\hat{q}$ ，再去計算 $x - M * \hat{q}$ 就可以得到 $\hat{r}$ ，最後判斷是否需要減去 $M$。

:::warning
不過需要注意，如果 `concatenatedBinary()` 傳入的 `n` 值過大，導致 `ans` 在模運算之前超過 $b^{2k}$ 時，這個算法得出的結果會是錯誤的。
:::

#### 結果

依照 leetcode 給的範圍，令 `0 < i <= 100000` 依序傳入 `concatenatedBinary()` 中，並紀錄執行的時間，最後在重跑一次確認 barrett reduction 的結果與使用 `%` 的版本相同。

origin mod = 25.098516 s
barrett reduction mod = 23.573488 s
all test case is the same

結果確實使用 barrett reduction 的版本會跑得比使用 `%` 還要快。