# 2023q1 Homework2 (quiz2) contributed by < `csm1735` > ## 測驗 `1` ### 解釋程式碼原理 此題關鍵在於找出最高位元的 1 ，並將從此位元到最低位元的所有位元 set 為 1 ，再透過對 `x + 1` 來使其進位成 2 的冪的值。 舉例來說 `x` 如果是 $(0010$ $1010)_2$ ，需要先 set 成 $(0011$ $1111)_2$ ，再透過 `x + 1` 成為 $(0100$ $0000)_2$ 而因 `x` 為 64 位元的 `uint64_t` ，故最多需要右移 63 個位元。 因此程式碼為: ```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; } ``` ### 用 `__builtin_clzl` 改寫 ```c uint64_t my_next_pow2(uint64_t x) { int shift = 64 - __builtin_clzl(x); return 1UL << shift; } ``` `__builtin_clzl` 的功能為找出最高位的 1 前面總共有幾個 0 而透過 `shift = 64 - __builtin_clzl(x)` 可以算出 x 在二進位下的 bits 長度，那只要對 1 左移 shift 個位元，即可得到答案。 舉例來說， `x` = $(0010$ $1010)_2$ ，則 `shift` = 64 - 58 = 6 ，因此我們對 1 左移 6 個位元，即可得到答案 $(0100$ $0000)_2$ ### 對應的 x86 指令 ``` my_next_pow2: .LFB16: .cfi_startproc endbr64 bsrq %rdi, %rdi movl $64, %ecx movl $1, %eax xorq $63, %rdi subl %edi, %ecx salq %cl, %rax ret .cfi_endproc ``` 產生對應的 x86 指令，可以看到 `bsrq` 指令。 --- ## 測驗 `2` ### 解釋程式碼原理 此題關鍵在於 `len` 這個變數，代表的是當前 `i` 值在二進制表示下的 bits 長度，也影響到了 `ans` 每次需要左移幾個位元，以 `ans = 1 , i = 2` 為例，由於 `i` 的二進位表示為 $(10)_2$ ，也就是 `len` 為2，因此需先將`ans` 左移 2 位成 $(100)_2$ ，再將 `i` 的值 $(10)_2$ set 上去成 $(110)_2$ 。 而以下的 if 判斷影響到了 `len` 的值。 ```c if (!(DDDD)) len++; ``` 可以發現在 `i` 在增加為 2 的冪次時，長度也會增加，例如 `i` 從 `111` 變為 `1000` 時，因此這邊需要判斷 `i` 是否為 2 的冪次，正確程式碼應如下: ```c if (!(i & i - 1)) len++; ``` 如果 `i` 為 2 的冪次， `(i & i - 1)` 將為 0 ，即 `!(i & i - 1)` 為 1 。 接著則是將 `ans` 左移 `len` 個，並 set 上 `i` 的值。 ```c ans = (i | (ans << len)) % M; ``` ### 嘗試使用 `__builtin_{clz,ctz,ffs}` 改寫 ```c int myConcatenatedBinary(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; } ``` `__builtin_clz` 的功能為找出最高位的 1 前面總共有幾個 0 透過 `shift = 32 - __builtin_clz(x)` 可以算出 x 在二進位下的 bits 長度，也就是變數 `len` 的值，即可用其來算出 `ans` --- ## 測驗 `3` ```c const uint64_t *end = qword + len >> 3; ``` 這邊將 `len` 右移了 3 個位元，也就是等同於除以八，因為我們為了增加執行速度，需要一次處理 8 bytes ，這樣做可以算出能完整放入 64 bits 的共有幾組，至於不足 8 bytes 的則之後處理。 ```c count = (1 << 3) * (len / 8) - count; ``` `(1 << 3) * (len / 8)` 用來計算出總長度中能完整放入 64 bits 的 8 bytes 組共有幾個 bytes ，然後再減去 `count` (即 continuation bytes 的數量)。 ```c count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; ``` 最後再透過 `len & 7` 檢查是否有不足 8 bytes 的部份需要處理，如果有則透過 `count_utf8` 來計算出扣除 continuation bytes 的字元數量，然後再相加以得到結果。 --- ## 測驗 `4` ### 解釋程式碼原理 ```c bool is_pattern(uint16_t x) { if (!x) return 0; for (; x > 0; x <<= 1) { if (!(x & 0x8000)) return false; } return true; } ``` 上述程式碼一開始會先檢查 `x` 是否為 0 ，如果是則直接 `return 0;` ，之後迴圈內會將 `x` 左移一個位元，如果 `x` 為 0 則跳出迴圈，可發現如果 `x` 不為 0 且最高位不為 1 則會 `return false;` ，因此我們可看出 `x` 只有在以下形式會 `return true;` ``` 1000 0000 0000 0000 1100 0000 0000 0000 1110 0000 0000 0000 . . . 1111 1111 1111 1111 ``` 根據此性質，可以做以下的改寫 ```c bool is_pattern(uint16_t x) { const uint16_t n = ~x + 1; return (n ^ x) < x; } ``` 將 `~x + 1` (即 `-x`) 和 `x` 做 `xor` 並判斷是否會小於 `x` 這邊以 8 bits 情況下的 $(1110$ $0000)_2$ 和 $(1110$ $1010)_2$ 來當例子: $(1110$ $0000)_2$ `xor` $(0010$ $0000)_2$ = $(1100$ $0000)_2$ 這邊會將原先最低位的 1 給改成 0 ，所以會小於原本的 `x` $(1110$ $1010)_2$ `xor` $(0001$ $0110)_2$ = $(1111$ $1100)_2$ 這邊會將原先中間的 0 給改成 1 ，所以會大於原本的 `x`