# 2023q1 第 2 週測驗題 contributed by <[`tintinjian12999`](https://github.com/tintinjian12999)> #### 題目請參考 [2023q1 第 2 週測驗題](https://hackmd.io/@sysprog/linux2023-quiz2) ## 測驗一 ### 解釋程式碼的運作原理 考慮題目所給的程式碼 ```clike 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; } ``` 假設 `x` 初始為 `x = 010...000` (只有第二個 bit 為1，其餘63個bit皆為0) 在經過前七行的 `x |= x >> 1` 後， `x` 變為 `x = 011111111...000` ，此時為了增加填補1的效率可以一次將 `x` 與自身向右位移8個bit的結果做 bit-wise or ，由此得到的結果為 `x = 01111111111111111...000` ，因此 AAAA 為8，並依此類推將得到的結果再往右16 bit (因此 BBBB 的答案為16)與32 bit 做 bit-wise or 就能得到指定位數以下全部填補為1的結果，最後只要將 x 加 1 就能得到所要求的結果，因此 CCCC 為x + 1。 ### 用 __builtin_clzl 改寫 從[Other Built-in Functions Provided by GCC](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)裡的敘述 ``` Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined. ``` 可以知道 clzl 的作用是找出 x 裡最高位1左側為0的位元數，因此若要找出最接近且大於等於 2 的冪的值只需要將0x8000000000000000右移為0的位元數 - 1個單位即可 ```clike uint64_t next_pow2(uint64_t x) { int number = __builtin_clzl(x); return 0x8000000000000000 >> (number - 1); } ``` ### 對應的 x86 指令 ```clike .file "next_pow2.c" .text .p2align 4 .globl next_pow2 .type next_pow2, @function next_pow2: .LFB0: .cfi_startproc endbr64 movabsq $-9223372036854775808, %rax bsrq %rdi, %rcx xorq $63, %rcx subl $1, %ecx shrq %cl, %rax ret .cfi_endproc .LFE0: .size next_pow2, .-next_pow2 .ident "GCC: (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0" .section .note.GNU-stack,"",@progbits .section .note.gnu.property,"a" .align 8 .long 1f - 0f .long 4f - 1f .long 5 0: .string "GNU" 1: .align 8 .long 0xc0000002 .long 3f - 2f 2: .long 0x3 3: .align 8 4: ``` > 延伸問題 > * 在 Linux 核心原始程式碼找出類似的使用案例並解釋 ## 測驗二 ### 解釋程式碼的運作原理 考慮下述的程式碼 ```clike 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; } ``` 我們知道若 i 為2的次方時則用來表達該數的 bit 需要加1 (2 = $10_2$， 4 = $100_2$)，這裡的 ```clike if (!(DDDD)) len++; ``` 就是在做這件事情，由註解可以得知要判斷是否為2的次方只需要將最右邊的1移除後再觀察是否為0即可，若為0則代表為2的次方(2的次方在二進制下只會有一個1)。將最右邊的1移除可以透過對該數與自身 - 1的結果做 bit-wise AND 達成，因此這裡的 DDDD 為 `i &= (i - 1)`。 接下來考慮 ```clike ans = (i | (EEEE)) % M; ``` 我們知道模除運算是具有分配律的，因此在分析的過程中可以無視 `% M`的部分 (因為這裡的迴圈不會對模除的結果造成影響)，以下敘述的 `ans_bef` 是 `ans` 在做模除運算前的結果。 假設今天考慮 `n = 4` 的情形，當 `i = 1` 時 `ans_bef = 1`，當 `i = 2` 時 `ans_bef` 須為 `ans_bef = 110` ，可以看到需要將 `1` 往左移動兩個 bit 並將 `2` set 進去，同理 `i = 3` 時 `ans_bef = 11011`，當 `i = 4` 時 `ans_bef` 須為 `ans_bef = 11011100` ，需要將 `11011` 向左移動三個 bit 再將 `3` set 進去，由此可知 EEEE 的答案為 `i << len`。 > 延伸問題 > * 嘗試使用 __builtin_{clz,ctz,ffs} 改寫，並改進模除運算 ## 測驗三 ### 解釋程式碼的運作原理 ## 測驗四 ### 解釋程式碼的運作原理 透過觀察前四個符合程式碼的樣式(0x8000, 0xc000, 0xe000, 0xf000)可以發現，此段程式碼檢查的是1從最高位元開始重複，直到數值出現0之後接下來的 bit 皆需為0，如0b1100滿足樣式而0b1001則不滿足。 若只考慮4個bit，假設符合樣式的數值為 x ``` x = 0b1000 x = 0b1100 x = 0b1110 x = 0b1111 ``` 則 ``` ~x = 0b0111 ~x = 0b0011 ~x = 0b0001 ~x = 0b0000 ``` ``` ~x + 1 = 0b1000 ~x + 1= 0b0100 ~x + 1 = 0b0010 ~x + 1 = 0b0001 ``` ``` (~x + 1) ^ x = 0b0000 (~x + 1) ^ x = 0b1000 (~x + 1) ^ x = 0b1100 (~x + 1) ^ x = 0b1110 ``` 可以發現上述行為實際上是將x最右邊的 bit 刪除，此行為可以保證得到的結果必定小於原始的 x ，因此 EEEE = ~x + 1， FFFF 為 x 。 > 若數值不滿足樣式，則此結果不成立。 > 延伸問題 > * 在 Linux 核心原始程式碼找出上述 bitmask 及產生器，探討應用範疇 參見 Data Structures in the Linux Kernel