# 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` 程式碼部分前七行皆為 ```c x |= x >> 1; ``` 這個連做 7 次後，會得到第一個 `1` 之後的 7 個位元也接著會是 `1` ，因此得到了至少連續 8 個`1` 在一起的數列，那之後就也不用慢慢的只位移一個位元了，我們可以一次位移 8 個位元了 ```c x |= x >> 8; ``` 之後就會得到從第一個 `1` 開始數，共連續 16 個 `1` 連在一起的數列，以此類推，等等可以直接位移 16 個位元，再來就是 32 個位元了。 做完上述的行為後，我們得到了第一個 `1` 開始之後，後面皆為 `1` 的數列，之後最後再加上 1 ，就可以得到大於輸入值，且為 2 的冪次的輸出值。 ```c 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)` 個位元就好了。 ```c 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 格來放進去。 ```c 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` 也應該用以計算的部分去減。 ```c count = (1 << 3) * (len / 8) - count; ``` 這部分就是檢查是否有剩餘的 byte 沒有被檢查到，如果有的話，那麼除以 8 就會有非零的餘數，就利用測驗 `3 `前面提到的 `count_utf8` 來計算剩餘的部分，如果 `len` 是 8 的倍數，則代表 for 迴圈就檢查完所有的 byte 了，就也不用再計算了。 ```c count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; ``` ## 測驗`4` :::success EEEE = `-x` FFFF = `x` ::: ### 程式碼原理 `is_pattern` 是要檢查輸入值以二進位表示，是否能分成左右兩部分，左邊皆為 `1` ，右邊皆為 `0`。 ```v 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`。 ```c x = 1111 1100 0000 0000 //input n = 0000 0100 0000 0000 //n = -x ^ n ^ x = 1111 1000 0000 0000 ^ ``` 可以發現，如果輸入值滿足條件，則它的二補數的形式是他的值最右邊的 `1` 的位子為 `1` ，其餘為 `0`，再與輸入值進行 xor ，會得到原本的輸入值，少了最右邊的 `1` ，其餘與原本一樣，因此會比原輸入值小。 再來觀察不滿足條件的狀況 : ```c x = 1111 1100 1000 0000 //input n = 0000 0011 1000 0000 //n= -x n ^ x = 1111 1111 0000 0000 ``` ```c 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` 。