# 2023q1 Homework2 (quiz2) contributed by < [WeiHongWi](https://github.com/WeiHongWi/quiz2/tree/master) > ## 測驗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 >> AAAA; x |= x >> 16; x |= x >> BBBB; return CCCC; }  </s> :::warning 不用列出填空的標示，只要列出值得討論的程式碼。 :notes: jserv > 已修改 ::: > [name=HongWei][time=Tue,Feb 28, 2023 8:35 PM] ### 程式碼原理 將 number x ~~**低於最靠近 most significant bit 且值為 1 的 bit 的所有 bit 都變成 1**~~. 的binary representation 中最高位的「1」及其右側的所有位數都變成「1」, 此時可以得知 number x 為 $2^k-1$,$k\in integer$ , 所以這時只要再加一就可以得到大於等於 number x 的最小 power of 2. :::info 粗體字的部份我會在想想怎麼表達 > ChatGPT 可幫助你 > :notes: jserv > 已修改 ::: 舉例來說：x = 01000....0000 x |= x >> 1 執行 7 次得到 x = 0x7f80000000000000,發現有 8 個 bits 值為1 x |= x >> 8 執行一次得到 x = 0x7fff800000000000,發現有16個 bits 值為1 x |= x >> 16 執行一次得到 x = 0x7fffffff80000000,發現有32個 bits 值為1 x |= x >> 32 執行一次得到 x = 0x7fffffffffffffff,發現此時目標達成 , 再 return x+1 則答案正確 ### 利用 __builtin_clzl() 改寫 __builtin_clzl() : 回傳 binary representation 中最高位的「1」及其左側為零的位元數 想法為利用 unsigned 右移補值為0的性質, x | 0xfff...fff 得到全為1 , 並左移 __builtin_clzl(x)一次之後, 再右移一次 __builtint_clzl(x) 來得到~~低於最靠近 most significant bit 且值為1的 bit 的所有 bit 都變成 1~~binary representation 中最高位的「1」及其左側全為零 舉例來說 x = 000...0101 , __builtin_clzl(x) = 61 11111....111 << 61 = 111 ... 000 111...000 >> 61 = 000 ... 111 此時 ans = x+1 = 8 c uint64_t next_pow2(uint64_t x) { int number = __builtin_clzl(x); x |= 0xffffffffffffffff; x = x<<number; x = x>>number; return x+1; }  和對應的 x86 指令  next_pow2: .LFB23: .cfi_startproc endbr64 bsrq %rdi, %rcx movq $-1, %rax xorq$63, %rcx salq %cl, %rax shrq %cl, %rax addq $1, %rax ret .cfi_endproc  --- ## 測驗 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 (!(DDDD)) len++; ans = (i | (EEEE)) % M; } return ans; }  ### 程式碼原理$mod(10^9+7)$還需要思考 1.DDDD = (i & (i-1)) ==0 i & (i-1) 可以用來判斷2種情況,是否為 **2 的 power**和 **unsigner or signed number** 2.EEEE = ans << len 舉例來說 x = 2 first loop ans = (1 | (0)<<1) % M = 1 second loop ans = (2 | 1 << 2) % M = 6 往左移動 len 個 bits 是為了裝下 i 的 binary representation ### 使用 __builtin_ {clz,ctz,ffs} 改寫 c int concatenatedBinary(int n) { const int M = 1e9 + 7; int len = 0; /* the bit length to be shifted */ long ans = 0; for (int i = 1; i <= n; i++) { // as all power of 2 only contains 1 set bit /*if (!(i^((i>>len)<<len))) len++;*/ len = len + (__builtin_ffs(i)-1==len); ans = (i | (ans<<len)) % M; } return ans; }  可以看到 len = len + (__ builtin_ffs(i)-1 == len) , __ builtin_ffs(i) 回傳 **i 中最靠右且為1的 bit的位置**. 假設為 x = 2,y=3 ,則 ___builtint_ffs(x) = 2, __builtint_ffs(y) = 1 , 可以發現除了 power of 2 以外的數的 __builtint_ffs() 都會小於 ___builtint_ffs(power of 2)，利用這個性質做到 i = power of 2 時才增加長度. 舉例來說, i = 4 ,len = 2 __ builtin_ffs(4)-1 = 2 ==len 所以 len = len + 1 = 3 i = 5 , len = 3 則 __ builtin_ffs(5)-1 = -1 != len 所以 len = len + 0 = 3 . . . i = 8 , len = 3 則 __ builtin_ffs(8)-1 = 3 == len 所以 len = len + 1 = 4 以此類推. > [name=HongWei][time=Tue,Feb 28, 2023 9:44 AM] --- ## 測驗4 c bool is_pattern(uint16_t x) { const uint16_t n = EEEE; return (n ^ x) < FFFF; }  EEEE = ~(x)+1 FFFF = x ### 程式碼原理 is_pattern() 回傳此 uint16_t x 是否從 most significat bit 之後的 bits必須是連續的1. 舉例來說 0xfff0 :+1: 0xfff1:-1: x = 0xfff1 , n = 0x000f , n ^ x = 0xfffe , 則 n^x < x return false ~~還沒搞清楚為何要 +1 , 理解當中...~~ 可以得知 n = ~(x)+1 為 x 的 negative number in 2's complement , 則 n ^ x 可以想成一個 bit mask, for example,使得能夠符合 pattern 的 number 可以遮住它 x 本身最靠右且為1的 bits. > [name=HongWei][time=Mon,Mar 6, 2023 3:04 PM] 測驗5 ## 測驗4 ### 程式碼運作原理 c= int ceil_log2(uint32_t x) { uint32_t r, shift; x--; r = (x > 0xFFFF) << 4; x >>= r; shift = (x > 0xFF) << 3; x >>= shift; r |= shift; shift = (x > 0xF) << 2; x >>= shift; r |= shift; shift = (x > 0x3) << 1; x >>= shift; return (KKKK) + 1; }  從 r = (x > 0xFFFF) << 4 , 可以知道看 x 是否大於 16 bits 最大的數 , 也就是說 x 是否需要 17 bits 以上來表示 , 若為true , 則此時$log(x)$必定超過 16 , 也就是 r 現在的值 , 之後的 x >> r ,是要去考慮在 uint32_t x 中的前半的 16 個 bits.以此類推. 其中 x-- 的設計 ， 使得剛好為 2 的次方數的 number 不會受到 return + 1 的影響 ### 改進程式碼 首先可以發現當 x =1 , ceil_log2(x) = 1 , 這裡我認為以數學的定義來說,我認為是錯的,畢竟$log(1) = 0$且$log(0)~is ~undefined$, 所以我定義當輸入 x=0 和 x=1 時,答案變成 1. 將 x 代 0 進入 , x 變為$2^{31} -1 = 4294967295\$ , 所以答案變成 32.所以若要改善這個問題從 x-- 這個 statement 下去考量.直觀的作法一定是用 if statement 去解決這個例外. 為了避免 x-- 的寫法 , 我利用 __builtin_ctz() 來去計算最靠近尾端且 bit 值為1,我假設為第 y 個 bit,則為了做到 x- -, 則將 0~y-1 個 bits 都變成 1,而其餘的 bit 都變成 0, 這樣才能避免 overflow 的問題. 其中設計第 y-1 個 bit 也為 0 是因為利用 x ^= mask , 使得第 y 個 bit 因為 exclusive OR 而變成 0,舉例來說 x = 16 = 0x00000010~16~ , __builtin_ctz(x) + 1 = 5 mask << 27 >> 27 = 0x0000001f x ^= mask = 0x0000000f 來得到 x-- 的效果且可以避免 overflow c= int last_position = __builtin_ctz(x)+1; uint32_t mask = 0xffffffff; mask = mask << (32 - last_position); mask >>= (32 - last_position); x ^= mask;