2023q1 Homework2 (quiz2)

contributed by <kart81604>

測驗1

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 改寫

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

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

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

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 。