# 2023q1 Homework2 (quiz2) contributed by < peter91015 > > [題目](https://hackmd.io/@sysprog/linux2023-quiz2) ## 測驗一 ### 解釋程式碼 原來的程式碼如下: ```c 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 >> 8; x |= x >> 16; x |= x >> 32; return x+1; } ``` 程式碼到 return 之前的動作都在將 `x` 在 leading 0-bits 以前的所有位元皆設成 1。 在不考慮 x==0 的情況下, `x |= x >> 1` 可以將最高位元的 1 下一個位元也設成 1 ,再做一次便可以將再下一個位元也設成 1 , 如此重複 7 次可確保最前面八個位元必定為 1 ,接著 `x |= x >> 8` 可以將再往後面八位的位元也設成 1 形成最多 16 個 1, `x |= x >> 16` `x |= x >> 32` 也是相似的操作,便可以把 leading 0-bits 以前的所有位元設為 1 ,其結果再加上 1 便是 大於 x 最小 2 的冪的數值。 ### 用 __builtin_clzl 進行改寫 ```c uint64_t next_pow2(uint64_t x) { return 1 >> (8*sizeof(x) - __builtin_clzl(x)-1); } ``` ## 測驗二 ### 解釋程式碼 原來的程式碼: ```c 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 (!(i&(i-1))) len++; ans = (i | (ans << len)) % M; } return ans; } ``` 迴圈內部主要在做的事情有兩個: * 判斷 i 是否為 2 的冪,代表在二進位之中有發生進位, `len` (記錄 i 的二進位表示的位元數)需要 +1 * 將 i 合併到 ans 裡面 要將 i 合併到 ans 裡面,我們需要先知道 i 的數值在二進位表示需要幾個位元,可以用變數 `len` 來記錄,而 `len` 的起始值為 0 ,只有 i 在二進位的表示之中有進位時 +1。在得知 i 的長度是多少後,我們就可以使用 `ans << len` 讓 `ans` 向左移出 i 所需要的位元數,再使用 `|` 運算子就可以把 i 合併進去。 而要判斷 i 是否為 2 的冪,可以使用 bitwise 操作 `i & (i-1)` ,其結果是將 i 去掉最右邊的 1 所得到的結果,如果是 0 就代表 i 為 2 的冪,同時也代表此時 i 在二進位表示有進位,需要讓 `len` +1 去更新 `len` 的數值。 ### 嘗試使用 __builtin_{clz,ctz,ffs} 改寫 ## 測驗三 ### 解釋程式碼原理 目標是算出有幾個 UTF-8 的字元,我們只需要找出有幾個 `continuation byte` ,再用 byte 的總數去扣除就可以得到字元的個數有多少。程式碼的架構是把原先一次處理一個 byte 變成一次處理八個 byte,最後如果未滿八個位元組則是套用到原本的 `count_utf8` 進行運算。 #### SWAR的處理方法 要找出 `continuation byte` ,我們只需要檢查每個 byte 之中的第 6 位元和第 7 位元(以 0 為開頭)並且符合 第 6 位元為 0 且第7位元為 1 ,可以參考[測驗三](https://hackmd.io/@sysprog/linux2023-quiz2) 的舉例說明 1~6;先對整個輸入做 not 運算並且對常數 0x40404040 做 & 運算(步驟 2、3),目的是為了消除第 6 位元和第 7 位元以外的所有資訊並且得到 `not bit6` 的結果(此結果為舉例說明中的 t2),接著步驟 4 讓 t2的位元向右移一個位元,並且步驟 5 讓原來的輸入(t0) 和 t2 做 & 運算,可以在每個 byte 的第 7 位元上得到 `bit7 and not bit6` 的結果,並且其他的位元都會為 0 ,所以 `continuation byte` 的個數可以整個結果之中 1 的個數來計算,步驟6 使用函式 `popcount` 來計算。 ## 測驗四 ### 解釋程式碼原理 這個函式的目的在於檢測輸入符合正規表示式 $1^+0^*$ 這樣的形式,意即 $1\cdots10\cdots0$ 或 $1\cdots1$ 的形式。原先的程式碼在檢測時會使用迴圈一直對輸入 x 進行左移直到 x 歸零,在歸零之前如果有檢測到最高位元為 0(和 0x8000 進行 & 運算判斷是否為 0),代表在前面的位元已經出現 0 的情況下後面還有 1 (否則整個數值為 0)。 後面改寫的程式碼原理則是,先取 n 為 x 的負數,意即 1 補數再 +1,如果輸入的樣式符合上述的型式的話,會得到除了最右邊1以外其餘都是 0 的結果,將 n 和 x 做 XOR 運算的話會使 x 最右邊的 1 設成 0 而使的 n^x 的結果必定小於 x。 舉例說明: ``` x = 1111 0000 n = 0001 0000 = -x n^x = 1110 0000 < 1111 0000 (把最右邊的 1 減去所以結果小於 x) ``` 如果是不符合輸入的樣式的話,意即連續的 1 之中會存在至少 1 個 0 ,在執行 n^x 的時候會使得夾在連續 1 之中的 0 被設成 1 導致得到的結果會比 x 來的大 舉例說明: ``` x = 1101 0000 n = 0011 0000 n^x = 1110 0000 > 1101 0000 (x^n 把原先夾在 1 裡面的"破洞(0)"補起來了 所以會讓結果大於x) ```