# 2023q1 第二週 quiz ## 第一題 完整程式碼 ```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; } ``` 本來看到一連串的 ```c x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; x |= x >> 1; ``` 不知道其用途，舉實際上的例子來搭配，才不會"舉燭" 取 x = 65 (010001) ``` x |= x >> 1;// x = 01100001 x |= x >> 1;// x = 01110001 x |= x >> 1;// x = 01111001 x |= x >> 1;// x = 01111101 x |= x >> 1;// x = 01111111 x |= x >> 1;// x = 01111111 ``` 可以發現一連串的操作就是從 most significant bit 開始逐漸填滿 1 ，而後面的 ```c x |= x >> 8; x |= x >> 16; x |= x >> 32; ``` 取 x = 140737488355328(2^47) 經過前面的 7 次 x |= x>>1 會變成 ``` 111111110000000000000000000000000000000000000000 ``` 做 ```c x |= x >> 8; ``` 變成 ``` 111111111111111100000000000000000000000000000000 ``` 得到 16 個 bit 都是 1 以此類推經過 ```c x |= x >> 16; ``` 變成 ``` 111111111111111111111111111111110000000000000000 ``` 再用 ```c x |= x >> 32; ``` 變成 ``` 111111111111111111111111111111111111111111111111 ``` 這樣只要最後的 x + 1 就是大於原先 x 的 2 的最小的冪次方，很適合用於來找分配 memory best fit 要多大 ### 用 __builtin_clzl 改寫 clz 就是 count leading zero 的意思，__builtin_clz(8)的返回值就是29，因為8的二進位制表示为0000 0000 0000 0000 0000 0000 0000 1000，其中前導0有2個9。 如果可以算前面有幾個 0 也可以很快地知道， most significant 的 1 在哪邊，可改寫成 ```c uint64_t next_pow2_clz(uint64_t x) { return 1<<(64 - __builtin_clzl(x)); } ``` ### 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？ 運用 ``` gcc -O2 -std=c99 -S next_pow2.c ``` 編譯，可以看到以下 machine code ``` next_pow2_clz: .LFB23: .cfi_startproc endbr64 bsrq %rdi, %rdi movl $64, %ecx movl $1, %eax xorq $63, %rdi subl %edi, %ecx sall %cl, %eax cltq ret .cfi_endproc .LFE23: ``` 可以發現，編譯出來的 machine code 並沒有多做額外的 function call，還可以看到 brsq 這個指令 好奇 ctz 的其他類似指令， ctz , ffs 會給哪些 x86指令呢 ctz ``` bsfq ``` ## 第二題 解釋 [leet code 1680. Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/description/) ```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 - 1)&i)) len++; ans = (i | (ans << len)) % M; } return ans; } ``` 其中 ```c if (!((i - 1)&i)) len++; ``` 是用來判斷是否為 2 的冪次方的判斷是，舉 16 為例 16 的 2 進位 10000 16 - 1 = 15 的 2 進位 01111 不難發現， 2 的冪次方與其 -1 的值完全沒有重複的 bit ，故其做 and operation 後必等於 0。 而 ```c ans = (i | (ans << len)) % M; ``` 表示每次要補上新的數字於 ans 後面時， ans 需要向左 shift len 的長度，騰出空間給新的數字 ### 嘗試使用 __ builtin_{clz,ctz,ffs} 改寫 如果一個數字為 2 的冪次方，表示其寫成 2 進位必定為 00...001..00，只有一個1，只是不確定 1 座落在哪個 bit 可以用 clz (count leading zero) 跟 ctz (count trailing zero) ，加起來後的值判斷其是不是等於 bit length - 1， 如果是就代表 1 只有出現一次，為 2 的冪次方。 ```c if((__builtin_clz(x) + __builtin_ctz(x)) == 31) len++; ``` 同理也可以用類似的概念 ffs (find first set) 來找到第一個 set (從右邊 lsb 數)的 1 ，搭配 clz 看兩者加起來是否等於 bit length 也會代表它就是 2 的冪次方 ```c if((__builtin_clz(x) + __builtin_ffs(x)) == 32) len++; ```