contributed by < kata1219
>
1
參照 你所不知道的 C 語言: bitwise 操作,考慮 next_pow2 可針對給定無號 64 位元數值 x,找出最接近且大於等於 2 的冪的值
AAAA = 8
BBBB = 32
CCCC = ++x
程式碼也可以改寫為
在 x 為 2 的冪時答案會錯誤,需要提前檢查 x 是否為 2 的冪
__builtin_clzl
改寫
int __builtin_clz (unsigned int x)
Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined.
int __builtin_clzl (unsigned long)
Similar to__builtin_clz
, except the argument type is unsigned long.
x |= x >> 1;
,代表 x 中為 1 的位元及其後面 7 位元共 8 位元設為 1。下一行的功能是將這 8 位元的 1 拓展一倍,以此類推,直到將 1 後面的 64 位元都設為 1。提示: 可執行
cc -O2 -std=c99 -S next_pow2.c
並觀察產生的next_pow2.s
檔案,確認 bsrq 指令 (表示 “Bit Scan Reverse”)
2
給定一整數 ,回傳將 1 到 的二進位表示法依序串接在一起所得到的二進位字串,其所代表的十進位數字 mod 之值。
DDDD = i ^ (i & ~(i - 1))
EEEE = ans << len
__builtin_{clz,ctz,ffs}
改寫,並改進 mod 的運算目前沒想到怎麼用 bitwise operation 實作 mod
3
SWAR 實作
AAAA = 3
BBBB = 7
CCCC = 7
DDDD = 0
4
以下程式碼可判定 16 位元無號整數是否符合特定樣式(在 leftmost set bit 左側的位元皆為 1 且 x 不為 0),將程式碼改寫為使用 bitwise operation。
EEEE = 0xFFFF
FFFF = (x & ~(x - 1))
參見 Data Structures in the Linux Kernel