# 2023q1 Homework2 (quiz2)
contributed by <`kart81604`>

## 測驗`1`
:::success
AAAA = `8`
BBBB = `32`
CCCC = `x + 1`
:::
### 程式碼原理
首先要將輸入值從左到右第一個出現 `1` 之後的位元都改成`1` ，如輸入
`x = 0100 0100 0100 0010` 應轉換為 `x = 0111 1111 1111 1111`
程式碼部分前七行皆為

x |= x >> 1;

這個連做 7 次後，會得到第一個 `1` 之後的 7 個位元也接著會是 `1` ，因此得到了至少連續 8 個`1` 在一起的數列，那之後就也不用慢慢的只位移一個位元了，我們可以一次位移 8 個位元了

x |= x >> 8;

之後就會得到從第一個 `1` 開始數，共連續 16 個 `1` 連在一起的數列，以此類推，等等可以直接位移 16 個位元，再來就是 32 個位元了。
做完上述的行為後，我們得到了第一個 `1` 開始之後，後面皆為 `1` 的數列，之後最後再加上 1 ，就可以得到大於輸入值，且為 2 的冪次的輸出值。

return x + 1

### 用 `__builtin_clzl` 改寫
::: success
`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_clz` 會回傳 `input` 最左邊有幾個連續 `0` ，那麼只要在 `unit64_t` 型別下，全部都是 `1` 的值，往右位移 `__builtin_clzl(x)` 個位元就好了。

uint64_t next_pow2(uint64_t x)
{
    return (0xFFFFFFFFFFFFFFFF >> __builtin_clzl(x)) + 1 ;
}

## 測驗`2`
:::success
DDDD = `i & (i - 1)`
EEEE = `ans << len`
:::
### 程式碼原理
設定輸入: n = 4 ，藉由題目描述，已知 n = 3，串接後為 `11011` ，接著要在此數列後新增 `100` ，因此要將原來的數列空出 3 格來放進去。

     vvv
11011

用來判斷要移出多少空格的參數為 `len` ，每經過2的冪次之後，要將 `len` 加 1 。
之後將 `ans` 往左位移 `len` 長度，再用 `|` 將要放入的值放進去，再 mod $10^9+7$ 。

## 測驗`3`
:::success
AAAA = 3
BBBB = 7
CCCC = 7
DDDD = 0
:::
### 程式碼原理
由於 `*end = qword + len >> 3` ，因此 `len` 要是不為 8 的倍數，會有一部分的 byte 沒有被計算到，因此for迴圈不一定有把 `*buf` 全部都檢查到。
由於我們每 8 個 byte 記錄一次，因此我們減掉 `count` 也應該用以計算的部分去減。

count = (1 << 3) * (len / 8)  - count;

這部分就是檢查是否有剩餘的 byte 沒有被檢查到，如果有的話，那麼除以 8 就會有非零的餘數，就利用測驗 `3 `前面提到的
`count_utf8` 來計算剩餘的部分，如果 `len` 是 8 的倍數，則代表 for 迴圈就檢查完所有的 byte 了，就也不用再計算了。

count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0;

## 測驗`4`
:::success
EEEE = `-x`
FFFF = `x`
:::
### 程式碼原理
`is_pattern` 是要檢查輸入值以二進位表示，是否能分成左右兩部分，左邊皆為 `1` ，右邊皆為 `0`。

1110 0000 0000 0000  //true
1111 1111 1000 0000  //true
1000 0000 0000 0000  //true
1000 1000 0100 0000  //false
     ^     ^
0000 0000 0000 0000  //false
1111 1111 1111 1111  //true

假設輸入值是滿足這個條件，也就是左邊部分為連續 `1` ，右邊部分為連續 `0`。

x     = 1111 1100 0000 0000 //input
n     = 0000 0100 0000 0000 //n = -x
              ^
n ^ x = 1111 1000 0000 0000
              ^

可以發現，如果輸入值滿足條件，則它的二補數的形式是他的值最右邊的 `1` 的位子為 `1` ，其餘為 `0`，再與輸入值進行 xor ，會得到原本的輸入值，少了最右邊的 `1` ，其餘與原本一樣，因此會比原輸入值小。

再來觀察不滿足條件的狀況 :

x     = 1111 1100 1000 0000 //input
n     = 0000 0011 1000 0000 //n= -x
n ^ x = 1111 1111 0000 0000

x     = 1111 1100 1000 1000 //input
n     = 0000 0011 0111 1000 //n = -x
n ^ x = 1111 1111 1111 0000

可以觀察到，`n ^ x` 會得到除了原本為 `1` 位置，還多了好幾個 `1` ，因此會比原輸入值大。
原理如下，找出輸入值轉成二進位後，其中所有 `1` 中最右邊的位子。下例為 10 。

1234 5678 9012 3456 //position
xxxx xxxx x100 0000 //input

計算其二補數

1234 5678 9012 3456 //position
xxxx xxxx x100 0000 //input
yyyy yyyy y011 1111 //~x
yyyy yyyy y100 0000 //-x = ~x + 1
           ^^^ ^^^^ //same as input

可以觀察到，以 `-x` 最右邊的 `1` 開始往右，他的二補數部分都與原輸入值相同，之後進行 xor 運算後得出 :

1234 5678 9012 3456 //position
xxxx xxxx x100 0000 //input
yyyy yyyy y100 0000 //-x
1111 1111 1000 0000 //-x ^ x

如果 input 前面那串 xxx... ，皆為 `1`，那麼就會比 `-x ^ x` 大，如果其中有包含 `0` ，則會小於 `-x ^ x` 。