以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
以下哪一种技术是整数除2的最佳选择,为什么?
技巧1:
x = x >> 1;
技巧2:
x = x / 2;
这里x是整数。
第一个看起来像除法吗?不。如果你想除法,用x / 2。如果可能的话,编译器可以优化它使用位移位(它被称为强度减少),这使得它成为一个无用的微优化,如果你自己做它。
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.)
使用最能描述您要做的事情的操作。
如果你将数字作为一个比特序列来处理,请使用bitshift。 如果你把它当作一个数值,使用除法。
请注意,它们并不完全相等。对于负整数,它们可以给出不同的结果。例如:
-5 / 2 = -2
-5 >> 1 = -3
(ideone)
哪一个是最好的选择,为什么整数除以2?
这取决于你对最佳的定义。
如果你想让你的同事讨厌你,或者让你的代码难以阅读,我肯定会选择第一个选择。
如果你想把一个数除以2,就用第二个数。
这两者是不等价的,如果数字是负的或在更大的表达式中,它们的行为是不一样的——bitshift的优先级比+或-低,除法的优先级更高。
您应该编写代码来表达其意图。如果您关心的是性能,不要担心,优化器在这类微优化方面做得很好。
我同意其他答案,你应该支持x / 2,因为它的意图更清楚,编译器应该为你优化它。
然而,选择x / 2而不是x >> 1的另一个原因是,如果x是一个有符号int并且是负的,那么>>的行为是依赖于实现的。
ISO C99标准第6.5.7节第5项:
E1 >> E2的结果是E1位右移E2位位置。如果E1 无符号类型,或者E1有符号类型且值为非负值, 结果值为E1 /商的积分部分 2 e2。如果E1具有符号类型和负值,则结果值为 是由实现定义的。
我们有很多理由支持使用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。
我想说有几件事需要考虑。
Bitshift should be faster, as no special computation is really needed to shift the bits, however as pointed out, there are potential issues with negative numbers. If you are ensured to have positive numbers, and are looking for speed then I would recommend bitshift. The division operator is very easy for humans to read. So if you are looking for code readability, you could use this. Note that the field of compiler optimization has come a long way, so making code easy to read and understand is good practice. Depending on the underlying hardware, operations may have different speeds. Amdal's law is to make the common case fast. So you may have hardware that can perform different operations faster than others. For example, multiplying by 0.5 may be faster than dividing by 2. (Granted you may need to take the floor of the multiplication if you wish to enforce integer division).
如果您追求的是纯粹的性能,我建议您创建一些可以执行数百万次操作的测试。对执行进行多次采样(您的样本量),以确定哪一个在统计上最适合您的操作系统/硬件/编译器/代码。
就CPU而言,位移运算比除法运算快。 然而,编译器知道这一点,并将适当地优化到它可以的程度, 因此,您可以以最有意义的方式编写代码,并且知道您的代码是有意义的 有效地运行。但是请记住,由于前面指出的原因,在某些情况下,无符号整型可以比整型更好地优化。 如果你不需要符号算术,那么不要包含符号位。
让你的意图更清楚……例如,如果你想除法,使用x / 2,并让编译器将其优化为shift运算符(或其他任何运算符)。
今天的处理器不会让这些优化对程序的性能产生任何影响。
一般右移分为:
q = i >> n; is the same as: q = i / 2**n;
这有时被用来加快程序的速度,但以清晰度为代价。我觉得你不应该这么做。编译器足够智能,可以自动执行加速。这意味着,以清晰度为代价,你不会获得任何好处。
看看《实用c++编程》的这一页。
在性能方面。CPU的移位运算比除法运算快得多。 所以除以2或乘以2等都可以从移位运算中获益。
至于外观和感觉。作为工程师,我们什么时候变得如此依赖化妆品,连漂亮的女士都不用!:)
这个问题的答案取决于你工作的环境。
If you're working on an 8-bit microcontroller or anything without hardware support for multiplication, bit shifting is expected and commonplace, and while the compiler will almost certainly turn x /= 2 into x >>= 1, the presence of a division symbol will raise more eyebrows in that environment than using a shift to effect a division. If you're working in a performance-critical environment or section of code, or your code could be compiled with compiler optimization off, x >>= 1 with a comment explaining its reasoning is probably best just for clarity of purpose. If you're not under one of the above conditions, make your code more readable by simply using x /= 2. Better to save the next programmer who happens to look at your code the 10 second double-take on your shift operation than to needlessly prove you knew the shift was more efficient sans compiler optimization.
所有这些假设都是无符号整数。简单的移位可能不是你想要的符号。此外,DanielH提出了一个关于在ActionScript等特定语言中使用x *= 0.5的好观点。
X/Y是正确的…和" >> "移位运算符..如果我们想要二除一个整数,我们可以使用(/)被除数运算符。移位运算符用于移位位。
x = x / 2; x / = 2;我们可以这样用…
查看编译器的输出来帮助您做出决定。我在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”的清晰度。
然而,如果速度是你的目标,那就两种方法都试一试,把握好时间。几个月前,我做了一个位图卷积例程,它涉及到在一个整数数组中步进,并将每个元素除以2。我做了各种各样的事情来优化它,包括用“x>>1”代替“x/2”的老技巧。
当我计算这两种方式时,我惊奇地发现x/2比x>>1快
这是使用Microsoft VS2008 c++并打开默认优化。