为什么JDK使用位移而不是乘除法？

Question

我有以下问题：

如果问是否使用移位比使用乘法或除法更好，答案是让JVM进行优化。

例如：is-shifting-bits-faster-than-multiplying 现在我正在查看jdk源代码，例如Priority Queue，代码仅使用移位进行乘法和除法（有符号和无符号）。

鉴于SO中的帖子是有效答案，我想知道为什么jdk更喜欢使用移位？这与性能无关的微妙细节吗？我怀疑它必须与溢出乘法和除法有关，但我不确定。有人有想法吗？使用移位处理微妙的溢出问题更好吗？还是只是品味问题？

- Cratylus

Answer 1

我认为在这个具体的例子中，他们这样做是为了使用符号位。Java缺乏无符号类型，所以对于使用最高位的数字，不可能用a /= 2来模拟a >>> 1。请注意，代码在整个示例中仅使用>>>。我相当确定这是为了充分利用整个位范围。

- Sergey Kalinichenko

---

有没有可能展示一个例子？我很想了解。 - Cratylus

@user384706 嗯，这很容易。如果你只有一个有符号的移位运算符，可以参考这个示例来编写无符号移位运算符。 - Voo

@Voo：您链接的帖子没有使用 / 运算符。 - Cratylus

@user384706 同样的原则 - 保存符号，进行无符号/有符号计算，修正结果。基本上可以用任何计算方法来完成。 - Voo

@user384706 我的意思是仅使用 n/2 是不可能的。我通过结合 n/2、条件语句、按位 AND 和按位 OR 来模拟它，但这可能会导致性能上的显著损失。 - Sergey Kalinichenko

Answer 2

除了大多数系统上的移位操作比除法快之外，>>>执行无符号操作，而除法不执行。例如，如果您想要两个值的中间点，则需要使用>>>来避免溢出。（请参阅Arrays.binarySearch以获取类似的代码）

- Peter Lawrey

---

我想知道为什么你在第一句话中提到性能。JVM不会自动优化吗？这是我从其他SO线程中提到的理解。 - Cratylus

如果输入为负数，则除法不等同于移位，而且JVM不能始终证明输入为非负数，在这种情况下，它必须承受除法的影响。 - Louis Wasserman

@LouisWasserman：所以你的意思是我们必须始终使用移位运算符，因为JVM不会总是按照我们的期望进行优化？在我链接的SO线程中，我认为没有提到这一点。 - Cratylus

我认为JVM在已知输入为非负数的情况下可能会很聪明，但是(-1/2) == 0和(-1 >> 1) == -1 (而-1 >>> 1 == Integer.MAX_VALUE)，所以它不能仅仅用右移来替换除以2。 - Louis Wasserman

如果你除以一个总是2的幂次方的n，计算机不会知道这一点。如果你总是移位m，那么你所做的就很清楚了。如果你除以一个常数2，它将会和>>一样，但不同于>>>，因为在Java中没有无符号的除法。 - Peter Lawrey

Answer 3

使用Java移位运算的一些有效原因：

• 如果有可能在未优化的环境下运行，并且无法保证JIT编译器会为您进行必要的优化。虽然这种情况现在可能很少见，但在某些情况下仍然可能发生。
• 如果您真正需要进行位操作而不是数值操作-直接使用移位在源代码中更加清晰明了。
• 如果您需要无符号操作（例如，您可以轻松地执行无符号移位，但无法执行无符号除法）。

- mikera

---

我认为原因3就是为什么例如在优先队列实现中他们更喜欢移位的原因？ - Cratylus

Answer 4

这更多是品味的问题。有些人习惯于二进制操作，因为它们更加本质（在我个人编写的代码中也使用此类操作）。然而，从性能角度来看，这两种方法的行为相同（优化发生在编译时，因此使用移位操作将改善编译时间，但只是微小的一部分，可以忽略不计）。

编辑：正如通常发生的那样，每次回答问题时我都会学到新的东西：考虑this。它证明了为什么除以二并不能总是优化为移位操作。因此，我的上面的评论几乎完全是错误的，只要Java没有无符号类型。

- Boris Strandjev

---

更普遍地说：在Java中，JIT只能用移位来替换2的幂次方除法，如果它能保证数字是正数。如果不是，则需要更复杂的例程（基本上归结为3个移位和一个加法，用于无分支版本，或者是一个分支、加法和移位）。 - Voo