2023q1 Homework2 (quiz2)

--- tags: Linux Kernel --- # 2023q1 Homework2 (quiz2) contributed by < [`chun61205`](https://github.com/chun61205) > > [第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2) ## 測驗 1 ```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 >> AAAA; x |= x >> 16; x |= x >> BBBB; return CCCC; } ``` ### 解釋程式碼原理，並用 `__builtin_clzl` 改寫 #### 解釋程式碼原理該程式碼可以找出最近且大於 `x` 的 $2$ 的冪的值。簡單來說，此程式碼透過將 `x` 最大位數之後的位數全部都設成 $1$ 最後只需要再加上 $1$ 就可以得到最近且大於 `x` 的 $2$ 的冪的值。我們可以已最大情況為例，假設 `x=0b01XXXXXX` ，其中 `X` 代表值可以是 `0` 也可以是 `1` 。 ```c x |= x >> 1; // x = 0b011XXXXX x |= x >> 1; // x = 0b0111XXXX x |= x >> 1; // x = 0b01111XXX x |= x >> 1; // x = 0b011111XX x |= x >> 1; // x = 0b0111111X x |= x >> 1; // x = 0b01111111 x |= x >> 1; x |= x >> AAAA; x |= x >> 16; x |= x >> BBBB; ``` 因此可以判斷 `AAAA` 為 `1` ， `BBBB` 為 `32` ， `CCCC` 為 `x+1` 。且程式碼可以簡化為 ```c uint64_t next_pow2(uint64_t x) { x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16; x |= x >> 32; 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. ```c uint64_t next_pow2(uint64_t x) { int n = __builtin_clz(x); return 0x8000000000000000 >> (n - 1); } ``` --- ## 測驗 2 ```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 (!(DDDD)) len++; ans = (i | (EEEE)) % M; } return ans; } ``` ### 解釋程式碼運作原理該函式的的功能在於，給定一整數 $n$ ，回傳將 $1$ 到 $n$ 的二進位表示法依序串接在一起所得的二進位字串，其所代表的十進位數字 $mod 10^9+7$ 之值。該函式透過 `for` 迴圈尋訪 $1$ 到 $n$ 的整數，並透過 `len` 來判斷目前尋訪到的整數 `i` 的二進位表示法的位元數，只要 `i` 為`2` 的冪的值，則需長度會多 $1$ ，因此 `DDDD` 為 `x & (x - 1) == 0` ，最後，將 `i` 串接到 `ans` 最後面，因此 `EEEE` 為 `ans<<len` 。 --- ## 測驗 3 ```c size_t swar_count_utf8(const char *buf, size_t len) { const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len >> 3; 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); } count = (1 << AAAA) * (len / 8) - count; count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD; return count; } ``` ### 解釋程式碼運作原理該程式碼的功用在於使用 SWAR 來一次比較 $8$ 個位元，以判斷 `buf` 需要使用幾個 bytes 表示。程式碼的前兩行在設定迴圈的終點： ```c const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len >> 3; ``` 透過 `len >> 3` 也就是 `len / 8` 來表示 `buf` 有幾個 $8$ bytes。接著，利用 for 迴圈來一次取 $8$ bytes 檢查： ```c for (; qword != end; qword++) ``` 並透過以下一系列的操作以確認第 6 個位元組是否為 `1` 1. 輸入的位元組 ```c t0 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx] ^^^^^^^^^ continuation byte ``` 2. 反向運算 ```c t1 = ~t0 t1 = [11xx.xxxx|10xx.xxxx|01xx.xxxx|00xx.xxxx] ``` 3. 隔離反向的第 6 個位元 ```c t2 = t1 & 0x40404040 t2 = [0100.0000|0000.0000|0100.0000|0000.0000] ``` 4. 對第 6 個位元，向左位移 $1$ 個位元 (移至第 7 個位元的位置) ```c t3 = t2 + t2 t3 = [1000.0000|0000.0000|1000.0000|0000.0000] ``` 5. 進行 `~bit6 && bit7` ```c t4 = t0 & t3 t4 = [00xx.xxxx|01xx.xxxx|10xx.xxxx|11xx.xxxx] & [1000.0000|0000.0000|1000.0000|0000.0000] = [0000.0000|0000.0000|1000.0000|0000.0000] ^^^^^^^^^ the only non-zero byte ``` 6. 以 `__builtin_popcount` 計算有多少 `1` 最後再確認未能被 $8$ 整除的部分有多少 continuation bytes。 ```c count = (1 << AAAA) * (len / 8) - count; count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD; ``` 需要將 `len` 最右側的 $3$ 個 bits 設為 `0` 並減去 continuation bytes 數量，再將無法被整除的部分，使用 `count_utf8` 得到去除 continuation bytes 後的字元數，最後將其相加得到結果。因此可以判斷 `AAAA` 為 `3` ， `BBBB` 為 `7` ， `CCCC` 為 `7` ， `DDDD` 為 `0` 。 :::warning 能否改寫程式碼、使其行為相同？ :notes: jserv ::: --- ## 測驗 4 ```c #include <stdint.h> #include <stdbool.h> bool is_pattern(uint16_t x) { const uint16_t n = EEEE; return (n ^ x) < FFFF; } ``` ### 解釋程式碼運作原理只要將 pattern 換成二進位，便可得知 pattern 的規則： ``` 1000000000000000 1100000000000000 1110000000000000 ... 1111111111111111 ``` 如此一來只要以以下思路進行運算： 1. `~x + 1` ``` 1000000000000000 0100000000000000 0010000000000000 ... 0000000000000001 ``` 2. `(~x + 1) ^ x` ，也就是去掉最右邊的 `1` ``` 0000000000000000 1000000000000000 1100000000000000 ... 1111111111111110 ``` 3. 最後得出來的值，因為最右邊的 `1` 被去掉，必定會小於 `x` 因此可以得知， `EEEE` 為 `~x + 1` ， `FFFF` 為 `x` 。另外，值得注意的是，若 `x` 不為 pattern 則 `(~x + 1) ^ x` 並不會小於 `x` ： 1. 高位元並非從最高位元開始連續的 `1` ``` 0100000000000000 -> 1100000000000000 -> 1000000000000000 ``` 2. 低位元並非從最低位元開始連續的 `0` ``` 1100000000001000 -> 0011111111111000 -> 1111111111110000 ```

Read more

Approximaiton Algorithms

Bucket Sort

Counting Sort

Radix Sort