# 2023q1 Homework2 (quiz2) contributed by < `ItisCaleb` > ## 測驗 `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 >> 8; x |= x >> 16; x |= x >> 32; return 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; } ``` 這樣可以保證從原本最高位的 1 到最低位都被 set 最後我們再加 1 就會是比原本的數更大的 2 的冪 但有一個問題就是如果 `x` 本身就是 2 的冪的話 計算出來的結果並不為 `x` :::warning 改進漢語表達。 :notes: jserv ::: 接下來我們用 `__builtin_clzl` (count leading zero) 來改寫 並且使用 `__builtin_ctzl` (count trailing zero) 來修復結果並不會是本身的錯誤 由於當輸入為 0 的時候結果為 undefined 所以如果遇到 0 就直接return 1 ```c uint64_t next_pow2(uint64_t x) { if(!x) return 1; int lz = __builtin_clzl(x), tz = __builtin_ctzl(x); if(lz + tz == 63) return x; return 1<<(64-lz); } ``` 而當我們觀察 asm 的時候是可以看到 `bsrq` 指令的 ```c next_pow2: .LFB3: .cfi_startproc movl $1, %eax testq %rdi, %rdi je .L1 bsrq %rdi, %rdx xorl %ecx, %ecx movq %rdi, %rax xorq $63, %rdx rep bsfq %rdi, %rcx addl %edx, %ecx cmpl $63, %ecx je .L1 movl $64, %ecx movl $1, %eax subl %edx, %ecx sall %cl, %eax cltq ``` --- ## 測驗 `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 (!(i & (i-1))) len++; ans = (i | (ans << len)) % M; } return ans; } ``` `i-1` 可以讓從 rightmost set bit 到 0 之間的 bit 全部翻轉 ``` 7 1111 -> 6 1110 4 1000 -> 3 0111 ``` 於是只要做 `i & (i-1)` 便可清除 rightmost set bit 而每當遇到 `i` 為2的冪我們就把 `len` 加一 最後我們便可以把原本的 `ans` 往左位移再把 `i` 的 bit pattern 放上去 --- ## 測驗 `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 << 3) * (len / 8) - count; count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; return count; } ``` 用 SWAR 的手法便能一次比較 8 個 byte (64位元系統) ```c const uint64_t *qword = (const uint64_t *) buf; const uint64_t *end = qword + len >> 3; // len / 8 ``` `qword` 是把 char 指標轉換成一個 uint64_t 的指標 而 `end` 則是 `buf` 的結尾，因為現在是每 8 個 byte 去比對所以我們便對 `qword` 加上 `len / 8` ```c 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); } ``` 而這邊便是我們要去找符合 `not bit 6 and bit 7(10xxxxxx)` 的 bit pattern 因為一次比較 8 個 byte 所以 mask 才會是 `0x04040404040404040llu` 而 `count` 就是符合的 byte 數量 ```c count = (1 << 3) * (len / 8) - count; ``` 接著就是把我們處理過的 byte 數量減掉 `count` 最後由於 `buf` 並不一定就是 8 的倍數 所以我們要去處理剩下來的 `byte` `len & 7` 效果等同於 `len % 8` ``` count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; ``` 最終得到的 `count` 就是UTF-8字元的數量 透過簡單的實驗便能得知 `count_utf8` 跟 `swar_count_utf8` 的效率落差 ![](https://i.imgur.com/b5causF.png) :::warning 修改 x 座標軸標註文字，應為輸入的 UTF-8 字元數量，並注意字元序列，儘量用已有的文字 (例如擷取自 Wikipedia) 作為輸入。 :notes: jserv ::: --- ## 測驗 `4` ```c bool is_pattern(uint16_t x) { const uint16_t n = ~x + 1; return (n ^ x) < x; } ``` 我們要確認的是否從 MSB 到 RSB(rightmost set bit) 都是 1 如果中間有任何 0 的存在的話則不符合 pattern 所以只有像是下面舉例的才會符合 ``` 0x8000 1000000... 0xc000 1100000... 0xe000 1110000... 0xf000 1111000... 0xf800 1111100... ``` 接著要來解釋 `is_pattern` 的方法 我們先拿 4 個 bits 的例子當範例 ``` 1100 ``` 經過 `~x + 1` 後會變成 RSB 左邊的 bits 反轉的同時 右邊所有的 bits 保留跟原本的一樣 ``` 1 1 0 0 0 1 0 0 ^ 最低位的 set bit ``` 接著再跟 `x` 去做 xor 會變成左邊的 bits 都被 set 而 RSB 及右邊的 bits 都被 clear ``` 1 1 0 0 0 1 0 0 1 0 0 0 ``` 假如 MSB 到 RSB 中間有 0 的話 則最後 xor 出來的結果會讓原本 0 的地方變成 1 導致比 `x` 還大 ``` 1 0 1 0 0 1 1 0 1 1 0 0 ``` 所以我們最後用 `< x` 來判斷是否符合 pattern