--- tags: linux2023 --- # 2023q1 Homework2 (quiz2) contributed by <`D4nnyLee`> [2023q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2#%E6%B8%AC%E9%A9%97-2) ## 實驗環境 ```shell $ gcc --version gcc (Debian 12.2.0-14) 12.2.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 39 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 4 On-line CPU(s) list: 0-3 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i5-4460 CPU @ 3.20GHz CPU family: 6 Model: 60 Thread(s) per core: 1 Core(s) per socket: 4 Socket(s): 1 Stepping: 3 BogoMIPS: 6399.99 ``` ## 測驗 `1` ### 解釋程式碼原理 > 題目給的二分搜尋法的程式碼中，當 `x` 大於 $2^{63}$ 時，回傳值會是 $2^{63}$， > 並不符合大於等於 `x` 的要求，因此我假設 `x` 的範圍是 $0$ 到 $2^{63}$。 這題給定的答案如下： * `AAA`: `8` * `BBB`: `32` * `CCC`: `x + 1` 先解釋最簡單的例子，也就是 `x` 為 0，預期的回傳值為 1。 當 `x` 為 0 的時候，不難發現做完 `return` 之前的所有運算之後 `x` 還是必定為 0，因此回傳 `x + 1` 時也會是預期的 1。 接著來解釋 `x` 不為 0 的情況。為了方便解釋，我定義 $X_0$ 是 `x` 的 [MSB](https://en.wikipedia.org/wiki/Bit_numbering#Bit_significance_and_indexing)，$X_1$ 是 MSB 的下一個位元，而 $X_2, X_3, \dots$ 則以此類推，最後是 LSB 的 $X_{63}$。 假設 `x` 中最高位的 1 是 $X_i$，題目中一連串的 or 運算的目的就是為了要將 $X_i, X_{i + 1}, \dots, X_{63}$ 都設為 1。 首先利用這 7 行將 $X_{i + 1}, X_{i + 2}, \dots, X_{i + 7}$ 都設為 1（注意雖然這邊 `i + 1` 到 `i + 7` 都有可能大於 63，但是不影響結果）。 ```cpp x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; ``` 因為 $X_i$ 到 $X_{i + 7}$ 都已經被設為 1，所以這邊可以直接將 $X_{i + 8}$ 到 $X_{i + 15}$ 同時設為 1。 ```cpp x |= x >> 8; ``` 之後也都是同理，同時設定 $X_{i + 16}$ 到 $X_{i + 31}$ 與 $X_{i + 32}$ 到 $X_{i + 63}$ 為 1。 ```cpp x |= x >> 16; x |= x >> 32; ``` 最後因為 `x` 會是 `0...01...1` 的形式，因此 `x + 1` 必定是二的冪，而且唯一的 1 的位置會是在 $i - 1$，也就是說回傳的值會==大於== `x`，但是題目要求的回傳值卻是==大於或等於== `x`。 ### 嘗試修正問題 將程式碼作以下修改之後就可以修正輸入二的冪次時會回傳非預期的回傳值的問題。 ```diff @@ -3,6 +3,7 @@ uint64_t next_pow2(uint64_t x) { + --x; x |= x >> 1; x |= x >> 1; x |= x >> 1; @@ -13,7 +14,8 @@ uint64_t next_pow2(uint64_t x) x |= x >> 8; x |= x >> 16; x |= x >> 32; - return x + 1; + ++x; + return x | (!x); } ``` 回傳的部分使用 `x | (!x)` 是因為要特別處理 0 的情況（後面會再詳細說明），當輸入不為 0 時，`(!x)` 這項預期都會是 0，因此就相當於 `return x;`。 分成以下三種情況來分析（假設 `x` 中最高位的 1 的位置是 $i$）： * `x` 是二的冪 `--x` 之後最高位的 1 就會從 $i$ 變成 $i + 1$，經過後面一連串的運算之後回傳的二的冪的 1 的位置就會在 $(i + 1) - 1 = i$，所以就達成了==等於==的條件。 * `x` 為 0 `--x` 之後會因為 integer underflow 而使得 `x` 的值變為 $2^{64} - 1$，因為最高位的 1 之後的位元也都是 1，所以做完一連串的 or 運算之後 `x` 的值並不會改變，而最後回傳 `x + 1` 時則會因為 integer overflow 所以又會變回 0。 回傳的時候因為有 `(!x)` 這一項，所以回傳值會是 1 而不是 0。 * 其它 因為 `x` 有兩個以上的位元為 1，因此 `--x` 之後並不會影響到最高位的 1 的位置，回傳值的 1 的位置就會是在 $i - 1$，也就達成了==大於==的條件。 ### 使用 `__builtin_clzl` 改寫 ## 測驗 `2` ### 解釋程式碼原理 #### `DDD` 根據註解的解釋，我們需要判斷把 `i` 的最小的位元清除後，是否為零，如果是零的話就要把 `len` 的值加一。 首先我們需要找出 `i` 的最小的位元，在二補數的系統上我們可以使用 `i & -i` 來得到最小的位元。 接著我們需要把 `i` 的該位元清除，這個部分有兩種寫法，分別是 `i ^ (i & -i)` 以及 `i & ~(i & -i)`，這邊我選擇較簡短的 `i ^ (i & -i)` 的寫法。 最後我們需要判斷清除最小位元之後的 `i` 是否為零，因此判斷式就可以寫成 `if (!(i ^ (i & -i)))`，由此可知 `DDD` 的答案應該為 `i ^ (i & -i)`。 #### `EEE` 因為 `len` 代表 `i` 的二進位表示法的長度（不包含開頭的 0），因此把 `ans` 與 `i` 連接起來的方法就可以寫成 `(ans << len) | i`，所以 `EEE` 的答案就是 `ans << len`。 ### 使用 `__builtin_{clz, ctz, ffs}` 改寫 利用這些函式改寫的 `DDD` 分別為： * `__builtin_clz` `i ^ (1 << (31 - __builtin_clz(i)))` * `__builtin_ctz` `i ^ (1 << __builtin_ctz(i))` * `__builtin_ffs` `i ^ (1 << (__builtin_ffs(i) - 1))` 若不侷限於先找出 `i` 的最小位元之後再做清除，而是直接判斷 `i` 是否只有一個位元為 1，則又可以寫成以下解法： * `i << (__builtin_clz(i) + 1)` * `i >> (__builtin_ctz(i) + 1)` * `i >> __builtin_ffs(i)` ### 修正在 `int` 上位移 32 位的未定義行為 在[前面](#使用-__builtin_clz-ctz-ffs-改寫)提到了一些使用 `__builtin_` 函式的寫法，但是其實有些寫法是未定義行為。 當 `i` 的值為 1 時，`i << (__builtin_clz(i) + 1)` 其實就會變成 `i << 32`。 依據 C99 6.5.7:3 [ Bitwise shift operators ] > The integer promotions are performed on each of the operands. The type of the result is that of the promoted left operand. If the value of the right operand is negative or is greater than or equal to the width of the promoted left operand, the behavior is undefined. `i` 是 32 位元整數，所以從最後一句的敘述可以得知 `i << 32` 會是非定義行為。 我嘗試將 `i << (__builtin_clz(i) + 1)` 修改為 `(i << __builtin_clz(i)) << 1`，但是這樣又會遇到另一個未定義行為。 以下分別擷取自 C 語言規格書以及 GCC 的文件 * C99 6.5.7:4 [ Bitwise shift operators ] > The result of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are filled with zeros. If E1 has an unsigned type, the value of the result is E1 × 2^E2^, reduced modulo one more than the maximum value representable in the result type. If E1 has a signed type and nonnegative value, and E1 × 2^E2^ is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined. * GCC 4.5 [ Integers ] > The results of some bitwise operations on signed integers (C90 6.3, C99 and C11 6.5). > > Bitwise operators act on the representation of the value including both the sign and value bits, where the sign bit is considered immediately above the highest-value value bit. Signed ‘>>’ acts on negative numbers by sign extension. > > As an extension to the C language, GCC does not use the latitude given in C99 and C11 only to treat certain aspects of signed ‘<<’ as undefined. However, -fsanitize=shift (and -fsanitize=undefined) will diagnose such cases. They are also diagnosed where constant expressions are required. 因為 `i` 是有號整數並且是正整數，`i << __builtin_clz(i)` 會得到 `int` 無法表達的數字，而此行為在 C99 標準中是未定義行為，但是 GCC 文件中有提到實作並沒有完全依照標準來做，並且沒有明白的說明哪個未定義行為在 GCC 中是可行的。 #### 實驗 C99 6.5.7 裡面提到的兩種未定義行為。 使用以下程式碼來實驗。 ```cpp #include <stdio.h> int main(void) { int n; // UB in C99 6.5.7:3, right operand >= sizeof(int) printf("%d\n", 1 << 32); scanf("%d", &n); printf("%d\n", 1 << n); // UB in C99 6.5.7:4, the resulting value is larger than INT_MAX printf("%d\n", 1 << 31); scanf("%d", &n); printf("%d\n", 1 << n); return 0; } ``` 編譯後可以發現 `gcc` 只會警告 `1 << 32` 的部分。 ```shell $ gcc -o quiz2_2 quiz2_2.c quiz2_2.c: In function ‘main’: quiz2_2.c:32:22: warning: left shift count >= width of type [-Wshift-count-overflow] 32 | printf("%d\n", 1 << 32); | ``` 實際執行之後可以發現即使 `n` 輸入為 32，`1 << 32` 和 `1 << n` 的結果居然是不同的，由此可以看出在 `gcc` 中 `1 << 32` 是未定義行為。 ```shell $ echo 32 31 | ./quiz2_2 0 1 -2147483648 -2147483648 ``` 至於 `1 << 31` 的部分，可以發現前處理器計算的值和實際執行時算出來的值是相同的。 接著再從組合語言的角度來觀察 GCC 是怎麼做 `1 << n` 的，以下是上面的程式碼編譯完的組合語言中與 `1 << n` 有關的部分。 ``` 0x0000000000001201 <+60>: mov eax,DWORD PTR [rbp-0x4] 0x0000000000001204 <+63>: mov edx,0x1 0x0000000000001209 <+68>: mov ecx,eax 0x000000000000120b <+70>: shl edx,cl ``` 可以看到這邊位移是用 `shl` 這個指令，這個指令是把數字當作無號整數來做位移（注意在程式碼中 `<<` 的左邊是 `int`），所以 `1 << n` 其實也可以看成是 `(int) (((unsigned) 1) << n)`，而這樣的話其實就解決了 `int` 無法表示 $2^{31}$ 的那個未定義行為。 #### 修改後的完整程式碼 因為 `1 << 31` 在 GCC 中是有效的，所以 `DDD` 修改成 `i << __builtin_clz(i) << 1` 即可。 ```cpp 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 << __builtin_clz(i) << 1)) len++; ans = (i | (ans << len)) % M; } return ans; } ``` ### 改進 mod $10^9 + 7$ 的運算 這邊我直接使用以下程式碼搭配 `gcc` 的 `-O1` 選項來編譯，透過組合語言來觀察編譯器會如何改善模運算。 ```cpp #include <stdint.h> #include <stdio.h> int main(void) { const uint32_t M = 1e9 + 7; uint64_t n; scanf("%lu", &n); printf("%u\n", n % M); return 0; } ``` 與模運算有關的組合語言如下，可以看到改進後的作法只剩下減法、乘法以及位移運算。 ``` 0x0000000000001163 <+26>: mov rsi,QWORD PTR [rsp+0x8] 0x0000000000001168 <+31>: movabs rdx,0x89705f3112a28fe5 0x0000000000001172 <+41>: mov rax,rsi 0x0000000000001175 <+44>: mul rdx 0x0000000000001178 <+47>: shr rdx,0x1d 0x000000000000117c <+51>: imul rdx,rdx,0x3b9aca07 0x0000000000001183 <+58>: sub rsi,rdx ``` > `rsp + 0x8` 是 `n` 在 stack 中的位址 > `0x3b9aca07` 則是 $10^9 + 7$ 組合語言中有用到一個神奇的數字 `0x89705f3112a28fe5`，這個數字其實就是 $\left\lceil \frac{2^{93}}{M} \right\rceil$。 $n \mod M$ 又可以寫成 $n - \left\lfloor \frac{n}{M} \right\rfloor M$，上面的組合語言在做的其實就是先算出 $\left\lfloor \frac{n}{M} \right\rfloor$ 之後再求出最後的答案。 從組合語言裡面可以看出，$\left\lfloor \frac{n}{M} \right\rfloor$ 被改寫成 $\left\lfloor n \cdot \left\lceil \frac{2^{93}}{M} \right\rceil \cdot \frac{1}{2^{93}} \right\rfloor$，不難發現兩者是非常相似的，但因為 $M$ 在編譯時期就已經知道了，所以可以先算出 $\left\lceil \frac{2^{93}}{M} \right\rceil$（也就是 `0x89705f3112a28fe5`），而除以 $2^{93}$ 之後再取底的運算可以直接用 `>>` 做到，因此改成後者之後就可以在不使用除法指令的情況下算出結果。 $\left\lfloor \frac{n}{M} \right\rfloor$ 算完的結果存在 `rdx`，之後再將 `n` 減去 `rdx` 乘以 $M$ 的結果就是 $n \mod M$ 的答案。 ``` 0x000000000000117c <+51>: imul rdx,rdx,0x3b9aca07 0x0000000000001183 <+58>: sub rsi,rdx ``` > 最後 `rsi` 就是 $n \mod M$ ## 測驗 `3` ### 解釋程式碼原理 首先函式的輸入是一個 `char` 的陣列，`buf` 為指向該陣列的第一個元素的指標，而 `len` 則是陣列長度。 此陣列是由 UTF-8 的字元來組成，因此每個字元可能由許多的 `char` 組成，函式的回傳值就是陣列中的 UTF-8 字元的個數。 ```cpp size_t swar_count_utf8(const char *buf, size_t len) { ``` SWAR 的原理就是一次處理複數的位元組，因此這邊為了要有辦法一次存取 8 個 `char`，會先把 `buf` 轉型成 `uint64_t *`。 題目程式碼的這個部分有一個問題，就是 `len >> 3` 沒有被括號包起來，因此原本的程式碼等同於 `end = (qword + len) >> 3`，但實際上應該是要寫成 `end = qword + (len >> 3)` 才對，因為 `end` 代表的是 `qword` 陣列的結尾。 ```cpp const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + (len >> 3); ``` 接著使用 `for` 迴圈以 8 個位元組為單位來計算後續位元組（continuation byte(s)）的個數，並將結果紀錄於 `count`。 ```cpp size_t count = 0; for (; qword != end; qword++) { const uint64_t t0 = *qword; const uint64_t t1 = ~t0; const uint64_t t2 = t1 & 0x04040404040404040llu; const uint64_t t3 = t2 + t2; const uint64_t t4 = t0 & t3; count += __builtin_popcountll(t4); } ``` 每個 UTF-8 字元都由一個首位位元組以及 0 到 3 個後續位元組組成，因此可以發現把位元組個數減去後續位元組個數之後就可以得到 UTF-8 字元的個數。 到目前為止只有處理總共 `len` 個位元組中的前面八的倍數的部分，例如長度為 10，則只有前 8 個位元組有被處理到，後面 2 個則是未處理的狀態。 因此這邊要使用 `len - len % 8` 來扣掉 `count` 而不是直接 `len - count`。 ```cpp count = (1 << 3) * (len / 8) - count; ``` 最後要來處理剩下的位元組，也就是當 `len` 不為 8 的倍數時就用 `count_utf8` 來處理。 > 這邊使用到了 `n % 8` 等價於 `n & 7` 的技巧來省去模運算。 ```cpp count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; return count; } ``` ## 測驗 `4` ### 解釋程式碼原理 改寫完的程式碼如下： ```cpp bool is_pattern(uint16_t x) { const uint16_t n = -x; return (n ^ x) < x; } ``` 首先先來看 `is_pattern(0)`，回傳的結果會是 `0 < 0` 也就是 `false`，這符合改進前的程式碼的預期。 接著再來看 `x` 不為 0 的情況。 假設 `x` 中最低位的 1 是 $2^L$，在二補數系統中，`-x ^ x` 的結果會是把 `x` 的 $2^L$ 這個位元設為 0，並且將所有高於 $2^L$ 的位元都設為 1。 例如 `x = 50`，這時 $L$ 會是 1，從下面的範例中就可以看到 $2^L$ 被設為 0，並且 $2^L$ 左邊的位元都被設為 1。 ``` 0000000000110010 = 50 ^ 1111111111001110 = -50 ----------------------------- 1111111111111100 || |--> L \\--> L 左邊的位元被設為 1 ``` 若 `x` 是符合樣式的數字，則 `-x ^ x` 的結果其實就可以看成是 $x - 2^L$，所以 `(-x ^ x) < x` 的結果就會是 `true`。 若 `x` 不符合樣式，則 `-x ^ x` 必定會大於 `x`，因為 `-x ^ x` 至少會把一個 $2^L$ 左邊的位元設為 1，也因此 `(-x ^ x) < x` 會回傳 `false`。
Last changed by  
 
D4nnyLee
285

Read more

2023q1 Homework1 (lab0)

contributed by < D4nnyLee > 開發環境 $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 48 bits physical, 48 bits virtual

2/27/2023
2021 Week14 - Number Theory

最大公因數（Greatest Common Divisor） 每個整數都會有一個以上的因數，而兩個整數可能會有一些共通的因數， 其中最大的因數就被稱為最大公因數。 雖然 STL 中有現成的函式可以直接用，不過實作的演算法也很值得學習。 基本性質 $\gcd(a, b) = \gcd(b, a)$ $\gcd(a, b) = \gcd(a \ % \ b, b)$

5/14/2022
2021 Week4 - Search

寫程式時，我們時常會需要在一個陣列中找出某個元素的位置， 而根據不同的條件，可以用不同的演算法來加快尋找的速度， 下面都有給出適用的情境，記得先確認目前的情況是否符合。 為了方便起見，下文中的 $N$ 都一律代表被搜尋的陣列的長度， $a_i$ 代表陣列中的索引值為 $i$ 的元素（注意 $i$ 是從 $0$ 開始）。 線性搜尋法（Linear Search） 適用情境 :::success

11/19/2021
2021 Week5 - Sorting

寫程式時，我們時常會需要排序，例如當我們想使用二分搜的時候，我們先將陣列做排序之後就可以直接套用二分搜。 這週會介紹一些基本的排序演算法。 雖然 STL 中有好用的 std::sort()，但是學習這些演算法的概念還是對解題是有幫助的， 例如在第三週教材中就有提到合併排序（Merge Sort）能應用在逆序數對問題。 為了方便起見，下文中的 $N$ 都一律代表被搜尋的陣列的長度， $a_i$ 代表陣列中的索引值為 $i$ 的元素（注意 $i$ 是從 $0$ 開始）。

11/1/2021
Read more from D4nnyLee
Published on HackMD