以下哪一种技术是整数除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 / 2而不是x >> 1的另一个原因是,如果x是一个有符号int并且是负的,那么>>的行为是依赖于实现的。
ISO C99标准第6.5.7节第5项:
E1 >> E2的结果是E1位右移E2位位置。如果E1 无符号类型,或者E1有符号类型且值为非负值, 结果值为E1 /商的积分部分 2 e2。如果E1具有符号类型和负值,则结果值为 是由实现定义的。
一般右移分为:
q = i >> n; is the same as: q = i / 2**n;
这有时被用来加快程序的速度,但以清晰度为代价。我觉得你不应该这么做。编译器足够智能,可以自动执行加速。这意味着,以清晰度为代价,你不会获得任何好处。
看看《实用c++编程》的这一页。
只是加了一个注释
在一些基于vm的语言中,x *= 0.5通常会更快——尤其是actionscript,因为变量不需要被检查是否除以0。
使用最能描述您要做的事情的操作。
如果你将数字作为一个比特序列来处理,请使用bitshift。 如果你把它当作一个数值,使用除法。
请注意,它们并不完全相等。对于负整数,它们可以给出不同的结果。例如:
-5 / 2 = -2
-5 >> 1 = -3
(ideone)
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.)