[數學] 以移位運算代替除法(除數為2的冪次方)

除法指令在 CPU 中的執行周期相較於其它運算(加減乘等)長，所以會盡可能的找替代方案來算出除法結果。這裡討論的是，當除以一個 2 的冪次方數時，要怎麼減化過程，特別是被除數為負時的情況。

正常都應該知道 x >> k，代表 x 除以 2 的 k 次方。但這個結果只能保證在 x >= 0 時是對的，但若在 x < 0 時，可就不一定了！舉例來說，若

-12345 / 2^4 = -771.5625

我們想要取的是整數，即 -771。

接下來以位元運算來看

-12345 = 1100_1111_1100_0111 b

若定義 -12345 / 2^4 = -12345 >> 4

1100_1111_1100_0111 b >> 4 = 1111_1100_1111_1100 b = -772

這並不與我們想要(-771)的結果一樣，因為移位運算後的結果都是取 floor 後的值，即

x >> k = floor(x / 2^k)

當 x >= 0，我們要得到整數部份就要取 floor，這與移位運算的特性一致；而當 x < 0時，我們要得到整數部份就要取 ceil ，但移位運算是取 floor，所以就會有誤。

因此，我們需要找一個作完移位運算後，是相當於取 ceil (x / 2^k)的演算法。也就是當 x < 0，找一個函數f(x)滿足下列式子

(f(x)) >> k = ceil( x / 2^k)

參考網路上資料與個人整理，證明下列運算式的關係：

利用這個運算式，可以得到若 x < 0

ceil (x / 2^k) = floor ( (x + 2^k - 1) / 2^k) = (x + (2^k - 1)) >> k

計算機學習日記