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

前言

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

問題敘述

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

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

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

在以位元運算來看

$$-{12345}_{10}\gg 4_{10}=1100\mathrm{\_}1111\mathrm{\_}1100\mathrm{\_}{0111}_2\gg 4_{10}=1111\mathrm{\_}1100\mathrm{\_}1111\mathrm{\_}{1100}_2=-772$$

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

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

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

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

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

證明

目標

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

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

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

令

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

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

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

討論：

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

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

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

$${\displaystyle \frac{y}{y}}\le {\displaystyle \frac{r+y-1}{y}}\le {\displaystyle \frac{2y-2}{y}}$$$$1\le {\displaystyle \frac{r+y-1}{y}}<2$$$$floor({\displaystyle \frac{x+y-1}{y}})=floor(q+{\displaystyle \frac{r+y-1}{y}})=q+1=ceil({\displaystyle \frac{x}{y}})$$

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

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

得證

參考文獻

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