[Math] 以移位運算優化除數為 2 的冪次方的除法

前言

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

問題敘述

基本上 $x\gg k$ 等同於 $\dfrac{x}{2^k}$，但這個結果只能保證在 $x \geq 0$ 時是對的，若在 $x < 0$ 時，可就不一定了！舉例來說，若 $x=-12345$ 且 $k=4$

以除法運算來看，取整數後即 $-771$。

$$x\gg k=-12345\gg 4=\dfrac{-12345}{2^4}=-771.5625$$

在以位元運算來看

$$-12345_{10}\gg 4_{10}=1100\_1111\_1100\_0111_2 \gg 4_{10} = 1111\_1100\_1111\_1100_2 = -772$$

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

$$x \gg k = floor(\dfrac{x}{2^k})$$

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

因此，我們需要一個函數，當 $x < 0$ 時作移位運算後結果為 $ceil(\dfrac{x}{2^k})$ 的演算法

$$(x + (2^k - 1)) >> k$$

證明

目標

$$ceil (\dfrac{x}{2^k}) = (x + (2^k - 1)) \gg k$$

要證明上式，必須先證明下式成立，

$$ceil(\dfrac{x}{y})=floor(\dfrac{x+y-1}{y}), \ \textrm{if}\ x\ \in \mathbb{Z}\ \textrm{and}\ y\ \in \mathbb{Z^+}$$

令

$$x=qy+r,\ 0 \leq r\leq y-1$$

q 為除法商數且 r 為除法餘數。再將此試代入目標等式右邊

$$\dfrac{x+y-1}{y}=\dfrac{qy+r+y-1}{y}=q+\dfrac{r+y-1}{y}$$

討論：

case 1：如果 $x$ 可以被 $y$ 整除，則 $r=0$

$$floor(\dfrac{x+y-1}{y})=floor(q+\dfrac{y-1}{y})=q=ceil(\dfrac{x}{y})$$

case 2：如果 $x$ 不能被 $y$ 整除，則 $1\leq r\leq y-1$

$$\dfrac{y}{y}\leq \dfrac{r+y-1}{y}\leq \dfrac{2y-2}{y}$$ $$1\leq\dfrac{r+y-1}{y}<2$$ $$floor(\dfrac{x+y-1}{y})=floor(q+\dfrac{r+y-1}{y})=q+1=ceil(\dfrac{x}{y})$$

最後，再利用這個等式，可以得到若 x < 0

$$ceil (\dfrac{x}{2^k}) = floor ( \dfrac{x + 2^k - 1}{2^k}) = (x + (2^k - 1)) \gg k$$

得證

參考文獻

1. 計算機中如何實現除數是2的冪次的除法