# 2023q1 Homework1 (quiz2) contributed by `JoshuaLee032190` ### 測驗一 * 根據題目的名稱`next_pow2`，我們可以知道這個題目要找出當前整數的下一個2 的冪整數。 * 題目如下： ```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; } ``` * 要回答這個問題首先可以直接看 pattern，可以看到前面總共做了7次 `x |= x >> 1`，而且`AAAA`的下一行為 16，由此我們可以推測 `AAAA` 為 8 * `BBBB` 為 32 * `CCCC` 就要從前面想了，前面的意思為==把這個整數的某一個位元往右全部填滿 1==，那在全部都是1的狀況，我們只需要 `+ 1` 即可得出最終的結果 :::info 我覺得前面右移做了七次有點多此一舉，而測試後，其實可以把code 改成以下的狀況達到同樣的結果 ```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; } ``` ::: ### 延伸問題 #### 1. 解釋上述程式碼原理，並用 __builtin_clzl 改寫 ```c 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_clzl 改寫完成 uint64_t next_pow2_2(uint64_t x) { int hi = __builtin_clzl(x >> 32); int lo = __builtin_clzl(x); uint64_t res = 1; return (hi == 31) ? res << 31 - lo + 1 : res << 64 - hi; } ``` > #### 2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋 * 我先使用 `grep -r "roundup" *` 找出了 pci.h ```c # /include/linux/pci.h static inline int pci_rebar_bytes_to_size(u64 bytes) { bytes = roundup_pow_of_two(bytes); /* Return BAR size as defined in the resizable BAR specification */ return max(ilog2(bytes), 20) - 20; } ``` * 這段程式碼主要是為了要初始化及配置空間，其中`20`的數字代表了 1mb 的大小所以先取 `max` * 可以想像，回傳值是一個大於等於0的常數，如果回傳值為0，那就代表PCI只需要配置1MB的空間，反之，以回傳值來判斷需要多配置多少空間 #### 3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？ > 提示: 可執行 gcc -O2 -std=c99 -S next_pow2.c 並觀察產生的 > next_pow2.s 檔案，確認 bsrq 指令 (表示 “Bit Scan Reverse”) * 有產生bsrq ``` next_pow2_2: .LFB14: .cfi_startproc endbr64 shrq $32, %rdi movl $64, %ecx movl $1, %eax bsrq %rdi, %rdi xorq $63, %rdi subl %edi, %ecx salq %cl, %rax ret .cfi_endproc ``` ## 測驗二 ### 解釋題目 * 由題目敘述得知，這個 function 會回傳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 (!(DDDD)) len++; ans = (i | (EEEE)) % M; } return ans; } ``` * 由題目內的參數名稱以及 `ans = (i | (EEEE)) & M`可知，`len` 為往左移動的距離 * 而只有在一種條件下 `len` 才會需要 `+ 1`，此情況為： ```python # 考慮 1 - 10 的位元如下 1 : 0001 2 : 0010 3 : 0011 4 : 0100 5 : 0101 6 : 0110 7 : 0111 8 : 1000 9 : 1001 10: 1010 ``` * 我們可以仔細觀察位元進位的時刻，狀況為前一個數字和當前的數字做 `AND` 運算得到 0 的狀況 * 所以 `DDDD` 很明顯就是 i & (i - 1) * 而每次都需要更新當前的位元到 `ans` 中，可想而知 `EEEE` 為 `ans << len`，如此一來就可以把運算後的數字放入當前空下來的位元 ### 使用__builtin 改寫 * __builtin_ffs : 用來找出 LSB 的位置 ==從右邊開始數的第一個bit== * __builtin_clz : 用來找出 MSB 的位置 ==從左邊開始數的第一個bit== * __builtin_ctz : 回傳從右邊開始數有幾個0 ```c int concatenatedBinary(int n) { const int M = 1e9 + 7; int len = 0; long ans = 0; for (int i = 1; i <= n; i++) { len = 32 - __builtin_clz(i); ans = (i | (ans << len)) % M; } return ans; } ``` ## 測驗三 * 看不懂 待處理 ## 測驗四 ### 解釋程式碼 * `is_pattern` 主要是在看輸入的無號整數的編碼是否存在特定樣式 * 此特殊樣式為==從MSB開始往LSB存在連續1== * 前面的function 可以看到在迴圈中x 總是跟 0x8000 也就是 `1000000000000000` 做and，當位元還沒有被清空時，只要中間的連續1斷開則回傳`false` > 後面的function 則是找出這個pattern 會發生的事情 ``` # 我們來看一下這個 pattern (這個假設在 bit數為5的狀況) 10000 11000 11100 11110 11111 首先，題目很明顯告訴你有一個 xor 跟比大小；也就是我們必須往比大小的方向思考 那要怎麼樣才可以利用這個 pattern 比大小呢？ 我們只需要先取 x 的負數，如此一來可以得到 10000 ==> 10000 11000 ==> 01000 11100 ==> 00100 11110 ==> 00010 11111 ==> 00001 此時 x ^ -x 就會變成 00000 10000 11000 11100 11110 最後再與原本的狀況比大小，此時，如果符合這個 pattern 的話，結果一定會比原本的輸入還要小，此時只要比大小，回傳即可。 ``` `EEEE` 為 `-x` `FFFF` 為 `x` ### 在 linux kernel 中找此 bitmask * 待處理