contributed by < WeiHongWi >
不用列出填空的標示,只要列出值得討論的程式碼。
已修改
HongWeiTue,Feb 28, 2023 8:35 PM
將 number x 低於最靠近 most significant bit 且值為 1 的 bit 的所有 bit 都變成 1. 的binary representation 中最高位的「1」及其右側的所有位數都變成「1」, 此時可以得知 number x 為 , , 所以這時只要再加一就可以得到大於等於 number x 的最小 power of 2.
粗體字的部份我會在想想怎麼表達
ChatGPT 可幫助你
jservImage Not Showing Possible ReasonsLearn More →
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
已修改
舉例來說: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 都變成 1binary representation 中最高位的「1」及其左側全為零
舉例來說 x = 000…0101 , __builtin_clzl(x)
= 61
11111…111 << 61 = 111 … 000
111…000 >> 61 = 000 … 111
此時 ans = x+1 = 8
和對應的 x86 指令
還需要思考
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}
改寫可以看到 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
以此類推.
HongWeiTue,Feb 28, 2023 9:44 AM
EEEE = ~(x)+1
FFFF = x
is_pattern()
回傳此 uint16_t x 是否從 most significat bit 之後的 bits必須是連續的1.
舉例來說 0xfff0
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.
HongWeiMon,Mar 6, 2023 3:04 PM
測驗5
從 r = (x > 0xFFFF) << 4 , 可以知道看 x 是否大於 16 bits 最大的數 , 也就是說 x 是否需要 17 bits 以上來表示 , 若為true , 則此時 必定超過 16 , 也就是 r 現在的值 , 之後的 x >> r ,是要去考慮在 uint32_t x 中的前半的 16 個 bits.以此類推.
其中 x– 的設計 , 使得剛好為 2 的次方數的 number 不會受到 return + 1 的影響
首先可以發現當 x =1 , ceil_log2(x) = 1 , 這裡我認為以數學的定義來說,我認為是錯的,畢竟 且 , 所以我定義當輸入 x=0 和 x=1 時,答案變成 1.
將 x 代 0 進入 , x 變為 , 所以答案變成 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 = 0x0000001016 , __builtin_ctz(x) + 1 = 5
mask << 27 >> 27 = 0x0000001f
x ^= mask = 0x0000000f
來得到 x– 的效果且可以避免 overflow