以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
当前回答
在性能方面。CPU的移位运算比除法运算快得多。 所以除以2或乘以2等都可以从移位运算中获益。
至于外观和感觉。作为工程师,我们什么时候变得如此依赖化妆品,连漂亮的女士都不用!:)
其他回答
使用最能描述您要做的事情的操作。
如果你将数字作为一个比特序列来处理,请使用bitshift。 如果你把它当作一个数值,使用除法。
请注意,它们并不完全相等。对于负整数,它们可以给出不同的结果。例如:
-5 / 2 = -2
-5 >> 1 = -3
(ideone)
我们有很多理由支持使用x = x / 2;以下是一些例子:
it expresses your intent more clearly (assuming you're not dealing with bit twiddling register bits or something) the compiler will reduce this to a shift operation anyway even if the compiler didn't reduce it and chose a slower operation than the shift, the likelihood that this ends up affecting your program's performance in a measurable way is itself vanishingly small (and if it does affect it measurably, then you have an actual reason to use a shift) if the division is going to be part of a larger expression, you're more likely to get the precedence right if you use the division operator: x = x / 2 + 5; x = x >> 1 + 5; // not the same as above signed arithmetic might complicate things even more than the precedence problem mentioned above to reiterate - the compiler will already do this for you anyway. In fact, it'll convert division by a constant to a series of shifts, adds, and multiplies for all sorts of numbers, not just powers of two. See this question for links to even more information about this.
简而言之,当你真正想要进行乘法或除法运算时,编写移位代码并没有什么好处,除了可能会增加引入错误的可能性。自从编译器不够聪明到在适当的时候优化这类事情到移位以来,已经过去了。
我说这些是为了参加编程比赛。一般来说,他们有非常大的输入,除以2会发生很多次,已知输入是正的或负的。
X >>1比X /2好。我在ideone.com上运行了一个程序,其中发生了超过10^10除以2的运算。X /2花了将近5.5s,而X >>1花了将近2.6s。
查看编译器的输出来帮助您做出决定。我在x86-64上使用 gcc (gcc) 4.2.1 20070719 [FreeBSD]
也可以在godbolt上看到编译器的在线输出。
What you see is the compiler does use a sarl (arithmetic right-shift) instruction in both cases, so it does recognize the similarity between the two expressions. If you use the divide, the compiler also needs to adjust for negative numbers. To do that it shifts the sign bit down to the lowest order bit, and adds that to the result. This fixes the off-by-one issue when shifting negative numbers, compared to what a divide would do. Since the divide case does 2 shifts, while the explicit shift case only does one, we can now explain some of the performance differences measured by other answers here.
C代码与汇编输出:
对于除法,你的输入是
int div2signed(int a) {
return a / 2;
}
这个编译成
movl %edi, %eax
shrl $31, %eax # (unsigned)x >> 31
addl %edi, %eax # tmp = x + (x<0)
sarl %eax # (x + 0 or 1) >> 1 arithmetic right shift
ret
shift也是一样
int shr2signed(int a) {
return a >> 1;
}
输出:
sarl %edi
movl %edi, %eax
ret
其他isa即使不能做得更好,也能同样有效地做到这一点。例如GCC For AArch64使用:
add w0, w0, w0, lsr 31 // x += (unsigned)x>>31
asr w0, w0, 1 // x >>= 1
ret
x / 2更清晰,x >> 1快不了多少(根据一个微基准测试,对于Java JVM快30%左右)。正如其他人所注意到的,对于负数,舍入略有不同,所以当您想处理负数时必须考虑这一点。一些编译器可能会自动将x / 2转换为x >> 1,如果他们知道这个数字不可能是负数(即使我无法验证这一点)。
即使x / 2可能不使用(慢)除法CPU指令,因为一些捷径是可能的,但它仍然比x >> 1慢。
(This is a C / C++ question, other programming languages have more operators. For Java there is also the unsigned right shift, x >>> 1, which is again different. It allows to correctly calculate the mean (average) value of two values, so that (a + b) >>> 1 will return the mean value even for very large values of a and b. This is required for example for binary search if the array indices can get very large. There was a bug in many versions of binary search, because they used (a + b) / 2 to calculate the average. This doesn't work correctly. The correct solution is to use (a + b) >>> 1 instead.)