# 2023q1 Homework2 (quiz2) contributed by<charlie0822> ## 開發環境 ```shell $ gcc --version gcc (Ubuntu 11.3.0-1ubuntu1~22.04) 11.3.0 $ lscpu Architecture: x86_64 CPU op-mode(s): 32-bit, 64-bit Address sizes: 36 bits physical, 48 bits virtual Byte Order: Little Endian CPU(s): 8 On-line CPU(s) list: 0-7 Vendor ID: GenuineIntel Model name: Intel(R) Core(TM) i7-3770 CPU @ 3.40GHz CPU family: 6 Model: 58 Thread(s) per core: 2 Core(s) per socket: 4 Socket(s): 1 Stepping: 9 CPU max MHz: 3900.0000 CPU min MHz: 1600.0000 BogoMIPS: 6784.20 ``` ## 測驗一 ```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 >> AAAA; x |= x >> 16; x |= x >> BBBB; return CCCC; } ``` 請補完程式碼，使其符合預期。 ### 想法與思考 自己先從8位元開始思考，`next_pow2(64)`=128，每向右一次就擴展一個0，擴展6次就會有連續7個1，最後加1進位就可以得到下一個2的冪 ``` 01000000 | v 01111111 (連續向右擴展 2 ) | v 10000000 (加１可以得到下一個 2 的冪) ``` 把邏輯帶入 64 位元的話就是要將 x 最高位元 1 後面位元都 set 成 1 ，最後加 1 進位到下一個 2 的冪返回。 `AAAA=8 BBBB=32 CCCC=x+1` ### 用 __builtin_clzl 改寫 ```c uint64_t next_pow2(uint64_t x) { return 1 << (64 - __builtin_clzl(x)); } ``` ## 測驗二 ```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 (!(DDDD)) len++; ans = (i | (EEEE)) % M; } return ans; } ``` 請補完程式碼，使其符合預期。 ### 想法與思考 if 判斷 i 是否是 2 的冪，因為當 i 是 2 的冪位元需要多一位，所以len需要加 1 ，在判斷中 DDDD 為 `i&(i-1)`，當 i 是 2 的冪時，i&(i-1)會剛好為 0 ，最後將ans向左移 len 將 i 加入到 ans 裡，故 EEEE為 `ans<<len`。 ### 使用 __builtin_{clz,ctz,ffs}改寫 ```c int concatenatedBinary(int n) { const int M = 1e9 + 7; int len = 0; long ans = 0; for (int i = 1;i <= n; i++) { if(__builtin_popcount(i)== 1){ len++; } ans = (i | ans << len) % M; } return ans; } ``` ``` Built-in Function: int __builtin_popcount (unsigned int x) Returns the number of 1-bits in x. ``` 當 i 是２的冪時，代表位元中只會有１個１,需要將 len 需要加１。 ## 測驗三 ```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 << AAAA) * (len / 8) - count; count += (len & BBBB) ? count_utf8((const char *) end, len & CCCC) : DDDD; return count; } ``` ### 想法與思考 一開始將 char *buf 轉換成 uint64，從處理 1 byte 改成可以 1 次處理８bytes, end 計算出總共有幾組的 8 bytes需要處理,進入迴圈開始計算 count 數，將字串長度減去 count 數就可以得到字元數量，由於 buf 不一定是 8 的倍數，最後有可能會有 0 ~ 7 個 bytes 需要處理, len % 8 = len & 7，故 `AAAA=3，BBBB=7，CCCC=7，DDDD=0`。 ## 測驗四 ```c #include <stdint.h> #include <stdbool.h> bool is_pattern(uint16_t x) { if (!x) return 0; for (; x > 0; x <<= 1) { if (!(x & 0x8000)) return false; } return true; } ``` 改寫上述程式碼，使其達到等價行為，但更精簡有效。 ```c bool is_pattern(uint16_t x) { const uint16_t n = EEEE; return (n ^ x) < FFFF; } ``` ### 想法與思考 先看看一開始的程式碼， x > 0 時將 x 向左位移1個，如果最高位元不是 1 return false，是 1 的話繼續迴圈，所以這個程式是從 MSB ( Most Significant Bit )檢查到 LSB ( Least Significant Bit )是否有連續的 1 。 了解程式邏輯後，就可以開始思考如何修改程式碼，n = ~x + 1，加 1 的目的將最右邊 1 的後面位元變得跟 x 一樣，將 n 跟 x 做 XOR，如果 MSB 沒有夾雜 0 的話， XOR出來的值必會小於 x，所以 `EEEE = ~x + 1 ， FFFF = x` 。 :::success 這邊用 4-bits 做說明 x = 1100 n = 0011 + 1 = 0100 x ^ n = 1000 < x :::