整数除以 2 的幂与右移的关系

整数除法与右移运算

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

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

例如

这里，那么只要对一个数，右移 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/
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/
0	1100111111001100	−12340	−12340.0
1	1110011111100110	−6170	−6170.0
4	1111110011111100	−772	−771.25
8	1111111111001111	−49	−48.203125

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

右移性质证明与优化

从上面 2 组数据中，我们可以看出右移结果为 向下 取整，即，如，

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

证明

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

假设 x 为 位整数，它的二进制表示如下：

那么

设

根据公式可得

已知一个数乘以 ，相当于 左移 位，那么有

两边同时除以 可得：

优化

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

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

现在给出公式，向上 取整转换为 向下 取整：

举个例子：

证明：

设，那么

也就是说，负数除以 ，首先加上，然后右移 位；而正数，直接右移 位。

综上所述：

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，就将 存入 eax 寄存器，然后对 eax 进行算数右移 3 位，最后返回 eax。

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

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