# 2023q1 Homework2 (quiz2) contributed by ??? ## 測驗 1 * `AAAA` = `8` * `BBBB` = `32` * `CCCC` = `x+1` ### 程式碼原理 這段程式碼的用處在於將最高位元的 `1` 填補到所有較低位元，最後再 +1 回傳 1. 一開始把最高 8 位元填補為 1 (包括最高位元) ```c x |= x >> 1; // x = 01000000000000000000000000000000 x |= x >> 1; // x = 01100000000000000000000000000000 x |= x >> 1; // x = 01110000000000000000000000000000 x |= x >> 1; // x = 01111000000000000000000000000000 x |= x >> 1; // x = 01111100000000000000000000000000 x |= x >> 1; // x = 01111110000000000000000000000000 x |= x >> 1; // x = 01111111000000000000000000000000 ``` 2. 接著一次填滿 8 個位元 (目前填補 16 位元) ``` x |= x >> 8; // x = 01111111111111100000000000000000 ``` 3. 接著一次填滿 16 個位元 (目前填補 32 位元) ``` x |= x >> 16; // x = 0111111111111111111111111111100 ``` 4. 最後一次填滿 32 個位元 ``` x |= x >> 32; // x = 0111111111111111111111111111111 ``` 5. 最後 +1 回傳 ``` return x+1; // x = 10000000000000000000000000000000 ``` ### `__builtin_clzl` 改寫 ```c uint64_t next_pow2(uint64_t x) { return x ? (1 << (64-__builtin_clzl(x))) : 1; } ``` ### 產生對應的 x86 指令 ``` next_pow2: .LFB0: .cfi_startproc endbr64 movl $1, %eax testq %rdi, %rdi je .L1 bsrq %rdi, %rdi movl $64, %ecx xorq $63, %rdi subl %edi, %ecx sall %cl, %eax cltq .L1: ret .cfi_endproc ``` 可以發現到指令中有 `bsrq` 指令，其作用為將暫存器中的數值從高位元到低位元搜尋，將遇到的第一個 `1` 位置，存入目標暫存器 ## 測驗 2 * `DDDD` = `i & (i-1)` * `EEEE` = `ans << len` ### 程式碼原理 ```c if (!(DDDD)) len++; ans = (i | (EEEE)) % M; ``` 題目要求是將 `1` 到 `n` 的二進位表示法依序串接在一起，因此可以很明顯的知道 `ans` 的值會是 `ans` 要經過右移 `len` 位後與 `i` 做 `|` 而 `len` 的增減只會在 `2` 的冪方時發生因此 `DDDD` 是一個可以判別 `i` 是否為 2 的冪方的表示式 當某數是 `2` 的冪方代表，除了最高位元以外都是 `0` 因此 `i & (i-1) == 0` 時代表 `i` 是 `2` 的冪方 ## 測驗 3 * `AAAA` = `3` * `BBBB` = `7` * `CCCC` = `7` ### 程式碼原理 ```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 的 pattern ，並且一次看 8 個 bytes ```c count = (1 << 3) * (len / 8) - count; count += (len & 7) ? count_utf8((const char *) end, len & 7) : 0; ``` 接著減去 count 就會是字串長度，但會有不是 8 的倍數的狀況，因此這裡需要處理不能被 8 整除的部份。 ## 測驗 4 * `EEEE` = `~x + 1` * `FFFF` = `x` ### 程式碼原理 這段程式碼用來確認某數 MSB 是否為第 16 個 bit，並且到最低的 set bit 中間是否都為 `1` ```c const uint16_t n = ~x + 1; return (n ^ x) < x; ``` 由上述程式碼可以發現，先對 `x` 做二補數，相當於保持最低有效位元並且對之後的位元做 `not` 。接著做 `(n^x)` 如果 `x` 符合 `pattern` 則該運算相當於 `x` 減去最低位元的二的冪次的數，若是不符合則是減去最低位元的二的冪次的數，再加上沒有連續位元的 bits * 符合 `pattern` ```c x = 0b11100 (n ^ x) = 0b11000 // 0b11100 - 0b100 ``` * 不符合 `pattern` ```c x = 0b100100 (n ^ x) = 0b111000 // 0b100100 - 0b100 + 0b11000 ``` 若是符合 `pattern` `(n ^ x)` 就會小於 `x`