# 2023q1 Homework2 (quiz2)

contributed by < `ShallowFeather` >
## 測驗 1

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

AAAA 為 8
BBBB 為 32
CCCC 為 x + 1
也能將該段 code 縮短成

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

可以這樣運算是因為可以知道當右移一位並做 `|` 運算後會將他的右項倍增
就像是
1000000 在跟 0100000 `|` 後會是 1100000
也因此可以直接將下一次運算時直接右移 2 位來節省運算次數。
以此類推。

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

DDDD 為 i & (i - 1)
EEEE 為 ans << len
`i & (i - 1)` 此操作將會移除最右邊的那個 `1`
那如果說他是 `2` 的冪次方就需要多一個 `bit` 來存他的二進位數值，因此將 `len++` 並在後面左移 len 位數並將 `i` 附加在 `ans` 右側

## 測驗 3

## 測驗 4

bool is_pattern(uint16_t x)
{
    const uint16_t n = EEEE;
    return (n ^ x) < FFFF;
}

EEEE = -x
FFFF = x
此題目要求為 確認 x 的 binary 是否符合在最右邊的 `1` 後皆為 `0`
-x 為 x 的二補數
EX:
如 x = 1100 0000 0000 0000 則他的補數為 0100 0000 0000 0000
因此並不會比 x 還要大
不過如果 x 為 1100 0000 0000 0001 其補數則為 0011 1111 1111 1111
則必定大於 x