整数除法与右移运算

在C/C++中进行除以2的幂的运算,学过计组的同学,可能会知道更高效的是进行右移运算,右移几位,相当于除以2的几次幂。

C/C++中整数除法,去除小数部分,整数部分作为返回结果。

例如$6/4=1, -6/4=-1$

这里$4=2^2$,那么只要对一个数,右移2位,就相当于除以4了么?

容易用如下代码验证:

#include <stdio.h>
int main(void) {
    printf("%d\n%d\n", 6>>2, -6>>2);
    return 0;
}

输出为

1
-2

显然当一个数为正数的时候,结果是正确的;但是当为负数的时候,貌似就不对了,这里可以多测试几组值:

k >> k (Binary) Decimal 12340/$2^k$
0 0011000000110100 12340 12340.0
1 0001100000011010 6170 6170.0
4 0000001100000011 771 771.25
8 0000000000110000 48 48.203125
k >> k (Binary) Decimal -12340/$2^k$
0 1100111111001100 −12340 −12340.0
1 1110011111100110 −6170 −6170.0
4 1111110011111100 −772 −771.25
8 1111111111001111 −49 −48.203125

那么如何优化,使右移对正负数都有效呢?

右移性质证明与优化

从上面2组数据中,我们可以看出右移结果为向下取整,即$x>>k = \lfloor \dfrac{x}{2^k} \rfloor$,如$12340>>4 = \lfloor \dfrac{12340}{2^4} \rfloor = \lfloor 771.25 \rfloor = 771$,$-12340>>4 = \lfloor \dfrac{-12340}{2^4} \rfloor = \lfloor -771.25 \rfloor = -772 \neq -771 = \lceil -771.25 \rceil$

那么,若要代替除法,当为正数的时候,应该向下取整;当为负数的时候,应该向上取整。

证明

现在给出证明:证右移运算为向下取整。

假设x为$w$位整数,它的二进制表示如下:
$$x = [x_{w-1}, x_{w-2}, \cdots, x_0]$$

那么$x=\sum_{i=0}^{w-1}x_{i} \times 2^i$


$$ \begin{align} x' &= [x_{w-1}, x_{w-2}, \cdots, x_{w-k}] \\ x'' &= [x_{k-1}, x_{k-2}, \cdots, x_{0}] \end{align} $$

根据公式可得
$$ x'' = \sum_{i=0}^{k-1}x_{i} \times 2^i \in [0, 2^k) $$

已知一个数乘以$2^n$,相当于左移$n$位,那么有
$$ x=2^k x’ + x’’$$

两边同时除以$2^k$可得:
$$ \begin{align} \dfrac{x}{2^k} &= x' + \dfrac{x''}{2^k} \\ \because x'' &\in [0, 2^k) \\ \therefore \dfrac{x''}{2^k} &= 0\\ \therefore \lfloor \dfrac{x}{2^k} \rfloor &= \lfloor x' + \dfrac{x''}{2^k}\rfloor = \lfloor x' \rfloor \end{align} $$

优化

已经证明了右移的性质,那么代替除法运算的时候,

当为正数的时候,应该向下取整;当为负数的时候,应该向上取整。

现在给出公式,向上取整转换为向下取整:
$$
\lceil \dfrac{x}{y} \rceil = \lfloor \dfrac{x+y-1}{y}\rfloor (y>0)
$$

举个例子:
$$ \begin{align} \lceil \dfrac{6}{4} \rceil &= \lfloor \dfrac{9}{4}\rfloor = 2\\ \lceil \dfrac{-6}{4} \rceil &= \lfloor \dfrac{-3}{4}\rfloor = -1 \end{align} $$

证明:

设$x=ky + r, 0\leq r< y$,那么

$$ 左边 = \lceil \dfrac{x}{y} \rceil = \lceil \dfrac{ky+r}{y} \rceil = k+\lceil \dfrac{r}{y} \rceil = \left\{ \begin{align} k, & r = 0 \\ k+1, & r \neq 0 \end{align} \right. $$ $$ 右边 = \lfloor \dfrac{x+y-1}{y}\rfloor = \lfloor \dfrac{ky+r+y-1}{y}\rfloor = k+\lfloor \dfrac{r+y-1}{y}\rfloor = \left\{ \begin{align} k, & r = 0\\ k+1, & r \neq 0 \end{align} \right. $$

也就是说,负数除以$2^k$,首先加上$2^k-1$,然后右移$k$位;而正数,直接右移$k$位。

综上所述:

result = (x<0 ? x+(1<<k)-1 : x) >> k

编译器行为

有此可知,对一个数除以2的幂,是不能随随便便右移的,还需要判断正负的,那么编译器会不会帮我们优化呢?

有如下代码:

int div(int x) {
    return x/8;
}

对其进行汇编(-O0无优化):

$ gcc -S -m32 -O0 div.c

截取如下汇编代码并注释:

movl    8(%ebp), %eax    # 将x存入%eax
leal    7(%eax), %edx    # 将x+7存入%edx
testl    %eax, %eax        # 判断x的正负
cmovs    %edx, %eax        # 若x<0,将x+7存入%eax
sarl    $3, %eax        # 算数右移3位

简而言之,上面代码首先将x存入eax寄存器,若x<0,就将$x+2^3-1=x+7$存入eax寄存器,然后对eax进行算数右移3位,最后返回eax。

result = (x<0 ? x+(1<<k)-1 : x) >> k

所以,编译器已经帮我们做好优化了,貌似没必要自己写右移来代替除法,这是个坑。