Java 编译器或JIT 编译器是否将除法或乘法优化为 2 的常数幂向下移位?
比如下面两条语句优化后是否是一样的?
int median = start + (end - start) >>> 1;
int median = start + (end - start) / 2;
(基本上是这个问题,但对于Java)
不,Java 编译器不会这样做,因为它无法确定
(end - start)
的符号是什么。为什么这很重要?负整数上的位移位会产生与普通除法不同的结果。在这里您可以看到一个演示:这个简单的测试:
System.out.println((-10) >> 1); // prints -5
System.out.println((-11) >> 1); // prints -6
System.out.println((-11) / 2); // prints -5
另请注意,我使用了
>>
而不是 >>>
。 >>>
是无符号位移,而 >>
是有符号的。
System.out.println((-10) >>> 1); // prints 2147483643
@Mystical:我编写了一个基准测试,表明编译器/JVM 没有进行该优化:https://ideone.com/aKDShA
如果 JVM 不会做,你也可以轻松自己做。
如上所述,负数右移的行为与除法不同,因为结果舍入到错误的方向。如果您知道股息是非负的,则可以安全地用移位代替除法。如果结果可能为负,您可以使用以下技术。
如果你能用这种形式表达你的原始代码:
int result = x / (1 << shift);
您可以用此优化代码替换它:
int result = (x + (x >> 31 >>> (32 - shift))) >> shift;
或者,另一种选择:
int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift;
这些公式通过添加根据被除数的符号位计算出的少量数字来补偿不正确的舍入。这适用于所有移位值从 1 到 30 的任何
x
。
如果移位为 1(即除以 2),则可以在第一个公式中删除
>> 31
,得到这个非常整洁的片段:
int result = (x + (x >>> 31)) >> 1;
我发现即使移位不恒定,这些技术也会更快,但显然如果移位恒定,它们受益最大。注意:对于
long
x
而不是 int
,请将 31 和 32 分别更改为 63 和 64。
检查生成的机器代码表明(毫不奇怪)HotSpot 服务器虚拟机可以在移位恒定时自动执行此优化,但(也毫不奇怪)HotSpot 客户端虚拟机太愚蠢了。