Java 是否将二的幂除法优化为位移位？

Question

Java 编译器或JIT 编译器是否将除法或乘法优化为 2 的常数幂向下移位？

比如下面两条语句优化后是否是一样的？

int median = start + (end - start) >>> 1;
int median = start + (end - start) / 2;

_{（基本上是这个问题，但对于Java）}

Answer 1

虽然公认的答案是正确的，因为除法不能简单地用右移代替，但基准是非常错误的。 任何运行时间少于一秒的 Java 基准测试都可能衡量解释器的性能 - 这不是您通常关心的事情。

我无法抗拒并写了一个自己的基准，主要表明它更加复杂。我并不是想完全解释结果，但我可以这么说

• 一般划分是一个非常慢的操作
• 尽可能避免它
• 除以常数会得到 AFAIK 总是以某种方式优化
• 除以 2 的幂被右移和负数调整取代
• 手动优化的表达式可能会更好

Answer 2

不，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

Answer 3

如果 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 客户端虚拟机太愚蠢了。