contributed by < chewei3
>
OP1
= >> 1
OP2
= m < 0
logical
用來判斷 >>
是 logical right shift 還是 arithmetic right shift ,如果 m < 0
且是 logical right shift ,則 fixu 為 -1u
,fix ^ (fix >> n)
用來將 m
shift 後的左邊 n
bits 補 1延伸問題:
OPQ
= 0x1
__builtin_ctz
回傳從 LSB 到第 1 個 1 之前有幾個 0,!(__builtin_ctz(num) 0x1)
判斷是不是偶數個, 所以 0x1、0x4、0x16… ,都會return 1, num & (num - 1)
用來判斷 num
是不是偶數,也就是判斷 LSB 是不是 1,所以可以去掉 0x1延伸問題:
x-compressor 是個以 Golomb-Rice coding 為基礎的資料壓縮器,實作中也用到 clz/ctz 指令,可參見 Selecting the Golomb Parameter in Rice Coding。
AAA
= __builtin_popcount(num)
BBB
= __builtin_clz(num)
numberOfSteps
計算最高位有效位的 bit position( 31 - __builtin_clz(num)
),加上 1 的個數( subtract 次數)延伸問題:
提示: Bit Twiddling Hacks 中提及許多 bitwise operation 的使用,如 bit inverse、abs 等等,是極好的參考材料。
考慮以下 64-bit GCD (greatest common divisor, 最大公因數) 求值函式:
改寫為以下等價實作:
XXX
= v
YYY
= u << shift
延伸問題:
可用 ctz 改寫為效率更高且等價的程式碼:
KKK
= bitset & -bitset
naive
的做法是一次只檢查 bitset 的某 1 bit 是不是 1,並且把bit position 放到 out[pos]
,每一個 bitmap 都要做 64 次效率不夠好improved
用 ctz 找出 bit position ,並且用 bitset & -bitset
將 bitset 的最低有效位的 1 設為 t ,用 xor 將之設為 0延伸問題: