以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
当前回答
在性能方面。CPU的移位运算比除法运算快得多。 所以除以2或乘以2等都可以从移位运算中获益。
至于外观和感觉。作为工程师,我们什么时候变得如此依赖化妆品,连漂亮的女士都不用!:)
其他回答
Mod 2, test for = 1。不知道c中的语法,但这可能是最快的。
一般右移分为:
q = i >> n; is the same as: q = i / 2**n;
这有时被用来加快程序的速度,但以清晰度为代价。我觉得你不应该这么做。编译器足够智能,可以自动执行加速。这意味着,以清晰度为代价,你不会获得任何好处。
看看《实用c++编程》的这一页。
查看编译器的输出来帮助您做出决定。我在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 = x / 2;或x /= 2;因为将来有可能会有一个新的程序员使用它。因此,他更容易发现代码行中发生了什么。每个人可能都不知道这种优化。
使用除法(/),假设这样更清楚。编译器将相应地进行优化。