# 2023q1 Homework2 (quiz2) contributed by <`Urbaner3`> ###### tags: `linux2022` `Linux Kernal` 測驗 `1` ------ ```cpp! 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 >> 1; /*add a line to make it work*/ x |= x >> AAAA; x |= x >> 16; x |= x >> BBBB; return CCCC; } ``` 將 x 右移並與 x 做或運算，會從有1的位數，右移後加回本為零的位數，增加顯示1的位元。題目有提示說到，依次右移1,2,4,8,16,32,64。因為一旦到達指定數字樣式，即1...1，右移多少位元，因為沒有零的位數，數字都不會變，且是我們要的樣式。若不是按照2的等比數列，如1,3,5,...中間會有零的位數，就不是冪減一了，不是全位數1的2進位數。所以 AAAA = 1。 奇怪這樣有落差，少了一行右移一，加入一行。AAAA = 8, BBBB = 32, CCCC = x+1 #### 延伸問題 1. 解釋上述程式碼原理，並用 [`__builtin_clzl`](https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html) 改寫 (程式POW) ```cpp! #include <stdint.h> static unsigned long int next_pow2(unsigned long int x) { int zs = __builtin_clzl(x); /*zeros;*/ return 1 << (sizeof(unsigned long int)-zs); } ``` 解釋如前段，為了得到相同輸出，直接對1做左移。 2. 在 Linux 核心原始程式碼找出類似的使用案例並解釋 [weak clz/ctz](https://github.com/torvalds/linux/commit/4df87bb7b6a22dfc6fdd5abb3dd362b3af2c164d) ```cpp! int __weak __clzdi2(long val) { return 64 - fls64((u64)val); } ``` [fls64](https://github.com/analogdevicesinc/linux/blob/master/tools/include/asm-generic/bitops/fls64.h) not in <linux/export.h, kernel.h> = linux/include/linux/kernel.h [better eq.](https://www.daemon-systems.org/man/fls64.3.html) 函數回傳由右向左數的非零位數，用64減去該數，得到左邊開始連續0的位數數量。 3. 當上述 clz 內建函式已運用時，編譯器能否產生對應的 x86 指令？ 參考 [aaron](https://hackmd.io/@aaron881011/rkZbh-zyn) ，執行 `cc` ```shell! .file "next_pow2.c" .text .ident "GCC: (Ubuntu 12.2.0-3ubuntu1) 12.2.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: ``` 沒有出現，圖例為對程式POW執行的結果。 測驗 `2` ------ 參考[作業](https://hackmd.io/@p4uHLG53RQ2mdlxeWiipWg/linux-2023-quiz2)發現 len 與 i 有關聯，但沒有進一步想到，一起合併，紀錄在 ans 並每次更新，以致於一時之間沒有發現。有些對2進位表示不習慣，我以為還要經過一個函數，有個固定語法的印象，一沒找到就認不出來，沒有想法了。也可說是對串接數字的方式沒有清楚的概念。 [實驗共筆](https://hackmd.io/PO1-iGQfT_OUQSFYUGkLLA?view#%E6%B8%AC%E9%A9%97-3) 測驗 `3` ------ 解釋原理： 因為2進位補數 0b10111111 是負數，所以更大的數，數值較小，第六第七位會是後續位元組開頭的樣式。所以用-65當作 magic number 這個演算法可以算出是否為後續位元組。 參考[範本](https://hackmd.io/@willwillhi/quiz2#%E6%B8%AC%E9%A9%97%E4%B8%89) AAAA=3, BBBB=7, CCCC=7 新演算法把8個數字串在一起，當作一個數字運算，如同題目開頭2數字串接的例子一樣，範本中，使用題目的說法，利用位元運算的性質，反轉再經過 mask 讓其他六位數字歸零，再繼續整理，讓目標樣式輸出一，計算一的數量。 [好解釋](https://hackmd.io/@yanjiew/linux2023q1-quiz2#%E6%B8%AC%E9%A9%97-3) 測驗 `4` ------ 參考[列表](https://hackmd.io/@willwillhi/quiz2#%E6%B8%AC%E9%A9%97%E5%9B%9B) ```shell! pattern: 0x8000 = 0b1000 0000 0000 0000 pattern: 0xc000 = 0b1100 0000 0000 0000 pattern: 0xe000 = 0b1110 0000 0000 0000 pattern: 0xf000 = 0b1111 0000 0000 0000 pattern: 0xf800 = 0b1111 1000 0000 0000 pattern: 0xfc00 = 0b1111 1100 0000 0000 pattern: 0xfe00 = 0b1111 1110 0000 0000 pattern: 0xff00 = 0b1111 1111 0000 0000 pattern: 0xff80 = 0b1111 1111 1000 0000 pattern: 0xffc0 = 0b1111 1111 1100 0000 pattern: 0xffe0 = 0b1111 1111 1110 0000 pattern: 0xfff0 = 0b1111 1111 1111 0000 pattern: 0xfff8 = 0b1111 1111 1111 1000 pattern: 0xfffc = 0b1111 1111 1111 1100 pattern: 0xfffe = 0b1111 1111 1111 1110 pattern: 0xffff = 0b1111 1111 1111 1111 ``` [同義解](https://hackmd.io/@ItisCaleb/HyTEU5j0i#%E6%B8%AC%E9%A9%97-4)， ```cpp! bool is_pattern(uint16_t x) { const uint16_t n = ~x+1; return (n ^ x) < x; } ``` 改寫程式碼為 pattern 的生成器： ```cpp! bool is_pattern(uint16_t x) { int n = __builtin_popcountll(x ^ 0x8000llu); uint16_t gen = 0x8000llu; for (int i=0; i<n; i++) gen |= gen>>1; return gen; } ``` 考慮到 0x8000 = $-2^{15}$ (mod $2^{16}$)，每一行都是前一行右移1位元，也就是除以二，這裡要邏輯位移，補上 MSB digit =1，所以新程式碼告訴我們邏輯位移的實做，`x |= x>>1`，我想也是除以2的實做。 x^-x = x<<1 = x * 2 = x - (-x)