# 2023q1 Homework2 (quiz2)
contributed by < `Damien-Chen` >

## 測驗一

### 說明
考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值，例如:

`next_pow2(7)` = 8
`next_pow2(8)` = 8
`next_pow2(13)` = 16

以 `next_pow2(7)` = 8 當例子。
7~(10)~ = 0000 0000 0000 0111~(2)~

我們只要將 0000 0000 0000 0111 + 1 = 0000 ... 1000 = 8~(10)~

再看 `next_pow2(13)` = 16
13~(10)~ = 0000 0000 0000 1101~(2)~
為了得到 0000 0000 0001 0000，可以進行以下操作

當 `x |= x >> 1` 後，結果為 : 0000 0000 0000 1111
再經過第二行 `x |= x >> 1` 後，結果仍不變。
那如果往右移 16 個位元呢? 其結果仍為不變。

也就是說，當以最高位元為起點往右看，所有 bits 都為 1 時 ，無論再向右位移多少 bits，結果都會是 0000 0000 0000 1111，所以只要在最後將其加 1 再 return 即可，可推得 CCCC = x + 1;

而往右移的方式則是依照1，2，4，8，16，32方式向右。所以推得 AAAA = 1，BBBB = 32。

由於 power of 2 必定為只有一個1，其餘全為0，該演算法的邏輯在於將其 MSB 右邊全部設為1，再加1。

int64_t next_pow2(uint64_t x)
{
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> 1;
    x |= x >> AAAA;
    x |= x >> 16;
    x |= x >> BBBB;
    return CCCC; // CCCC = x + 1
}

而要使用 `__builtin_clzl` 改寫，需先對其功能進行了解。
> `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.
> `int __builtin_clzl (unsigned long)`
> Similar to `__builtin_clz`, except the argument type is unsigned long.

`__builtin_clzl` 回傳 leading zero 的個數，舉例來說， `__builtin_clzl(7)` = 61，代表有 61 個連續的 leading zero，那剩下共有 64 - 61 = 3 個 bit 不為 0，那麼只需要將 2 乘 3 次即可。

再看 `__builtin_clzl(13)` = 60，剩下 4 個 bits 不為連續的零，將 2 乘 4 次 即可。

uint64_t next_pow2(uint64_t x)
{
    int n = __builtin_clzl(x);
    int non_zero = 64 - n;
    return pow(2, non_zero);
}

---

## 測驗二

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 (!(DDDD))
            len++;
        ans = (i | (EEEE)) % M;
    }
    return ans;
}

根據註解提示 : if it is power of 2, we increase the bit length。

因此 DDDD 為判斷是否為2的冪的式子，而2個冪代表二進位表示法中，只有一個1，其餘皆為0，因此，我們可以將 i 和 i - 1 進行 AND 運算，如果為0，代表是2的冪，反之則不是，原理如下:

假設 i = 8~(10)~ = 1000~(2)~
則 8 & (8 - 1) = 1000 & 0111 = 0000 = 0~(10)~

若 i = 7~(10)~ = 0111~(2)~
則 7 & (7 - 1) = 0111 & 0110 = 0110 = 6~(10)~

接著往下看，如果是 2 的冪我們就增加位元長度，但是這位元長度到底是要做什麼呢?

我們舉 n = 4 當作例子看看:
* i = 1 : 不是 2 的冪，因此 ans = 1;
* i = 2 : 是 2 的冪，此時 len = 2，而我們要把 10 接在 1 的後面，因此把1往左位移兩個位元。
* i = 3 : 不是 2 的冪，此時 len = 2，把 11 接在 10 後面，因此要再往左位移兩個位元。
* i = 4 : 是 2 的冪，此時 len = 3，把 100 接在後面，因此需要往左位移三個位元。

從上述的例子可以發現，每次遇到2的冪，我們要往左位移的位元就需要加一，因為每一個更大的2的冪都需要更多的位元來表示，因此可以推得 EEEE = ans << len。

接著由於往左位移，多出來的位元會補0，再與該 i 的值進行邏輯 OR 運算即可將其加再後面。

:::danger
注意書寫規範：中英文間用一個半形空白字元分隔。
:notes: jserv
:::