contributed by < `tab08222` >

## 測驗一
### 解釋程式碼運作原理
本題要考慮 next_pow2 可針對給定無號 64 位元數值 x，找出最接近且大於等於 2 的冪的值

int main()
{
    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 ;
}

依題目給定的程式碼可以發現，該段程式碼目的在於將最高位元後方的 bit 以 1 替代，最後 +1 來得到最接近的 2 的冪的值，因此:
`AAAA` : 8
`BBBB` : 32
`CCCC` : x+1

### 用`__builtin_clz`改寫
先用`__builtin_clz`找出msb， 接著以 64-msb 找到 input 之 msb 的更高一個位元，即`y`
再以`pow(2,64-y-1)`計算出冪值

uint64_t next_pow2(uint64_t x)
{
    int result,y;
    y = __builtin_clz(x);
    return pow(2,64-y-1);   
}

---

## 測驗二
### 解釋程式碼運作原理

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

`for` 迴圈內的功能在於判斷每一個數字需要用幾個位元(即 `len` )來表達，由於只有遇到 2 的冪值時，`len` 才會增加，因此 `if` 判斷式的目的即為判斷 `n` 是否為 2 的冪值，因此:
`DDDD` : `n&~2^log2(n)`
`EEEE` : `i<<len`

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

這裡以` __builtin_ctz` 來計算從右方數來共有多少連續個 0，藉此判斷n是否為 2 的冪的值

---

## 測驗三

---

## 測驗四
### 解釋程式碼運作原理

#include <stdint.h>
#include <stdbool.h>

bool is_pattern(uint16_t x)
{
    if (!x)
        return 0;

    for (; x > 0; x <<= 1) {
        if (!(x & 0x8000))
            return false;
    }

    return true;
}

該段程式碼可以判斷在輸入當中，是否可以找到一個 bit，使得其左方皆為 1，右方皆為 0
### 改寫上述程式碼，使其達到等價行為

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

令n的每個bit皆為1，再做 `n ^ x` ，此時若輸入為合法 pattern ，代表 1 集中在高位元，那麼`n ^ x` 會讓數值變小，若輸入不為合法 pattern，則代表有 0 出現在 1 前面，這時 `n ^ x` 會讓數值變大，因此:
`EEEE` : 65535
`FFFF` : x