contributed by < EdwardCKC
>
1
題目: 針對給定無號 64 位元數值 x
找出最接近且大於等於 2 的冪的值,例如:
next_pow2(6) = 8
next_pow2(15) = 16
next_pow2(64) = 64
x |= x >> 1
因為 >>
precedence 比 |
高,所以執行順序是 x = x | (x >> 1)
因為每做一次 x |= x >> 1
會向 LSB 多擴展 1 個 1
AAAA
之前會有 8 個 1, 而 AAAA
之後需要 16 個 1, 所以 AAAA = 8
同理 BBBB = 32
最後使 x
中 MSB 的 1 擴展到 LSB
然後 CCCC = x + 1
剛好進位到下一個 2 的冪的值。
但如果 || 答案會 +1 或 integer overflow, 所以要 x - 1
__builtin_clzl
改寫從 C 語言:數值系統的roundup_pow_of_two() 得知類似操作,
unsigned long __roundup_pow_of_two(unsigned long n)
Description
round the given value up to the nearest power of two - the result is undefined when n == 0 - this can be used to initialise global variables from constant data
從grep -r "rounddown_pow_of_two\|roundup_pow_of_two" linux-6.2.2/kernel/
找到 hashtab.c
的 htab_map_alloc
有類似的使用案例
在 line 493 利用 roundup_pow_of_two
確保 n_buckets
的大小是2的冪的值
在Compiler Explorer x86-64 gcc 11.3 執行, 結果有 bsrq
指令
2
len
是 int 在記錄 bit 的有效長度,只有
len
的長度可以用 bitwise 操作 !(i & i-1)
判定 i
的bit長度是否需要 len++
最後的 ans
是先把 ans
向左移動(ans << len
), 之後用 bitwise or 去把兩個值的 bit 接在一起再 mod M
利用 32 - __builtin_clz(i)
算出位移量,可以減少決定 len
的值的 if statement 和 len
參數
3
4