Does Java optimize division by powers of two to bitshifting?

Question

Does the Java compiler or the JIT compiler optimize divisions or multiplications by a constant power of two down to bitshifting?

For example, are the following two statements optimized to be the same?

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

_{(basically this question but for Java)}

Answer 1

While the accepted answer is right in the sense that the division can't be simply replaced by a right shift, the benchmark is terribly wrong. Any Java benchmark running for less than one second is probably measuring the interpreter's performance - not something you usually care about.

I couldn't resist and wrote an own benchmark which mainly shows that it's all more complicated. I'm not trying to fully explain the results, but I can say that

• a general division is a damn slow operation
• it gets avoided is much as possible
• division by a constant gets AFAIK always somehow optimized
• division by a power of two gets replaced by a right shift and an adjustment for negative numbers
• a manually optimized expression might be better

Answer 2

No, the Java compiler doesn't do that, because it can't be sure on what the sign of (end - start) will be. Why does this matter? Bit shifts on negative integers yield a different result than an ordinary division. Here you can see a demo: this simple test:

System.out.println((-10) >> 1);  // prints -5
System.out.println((-11) >> 1);  // prints -6
System.out.println((-11) / 2);   // prints -5

Also note that I used >> instead of >>>. A >>> is an unsigned bitshift, while >> is signed.

System.out.println((-10) >>> 1); // prints 2147483643

---

@Mystical: I wrote a benchmark, that shows that the compiler / JVM doesn't do that optimization: https://ideone.com/aKDShA

Answer 3

If the JVM does not do it, you can easily do it yourself.

As noted, right shifts on negative numbers do not behave the same as division because the result is rounded in the wrong direction. If you know that the dividend is non-negative, you can safely replace the division by a shift. If it might be negative, you can use the following technique.

If you can express your original code in this form:

int result = x / (1 << shift);

You can replace it with this optimized code:

int result = (x + (x >> 31 >>> (32 - shift))) >> shift;

Or, alternatively:

int result = (x + ((x >> 31) & ((1 << shift) - 1))) >> shift;

These formulae compensate for the incorrect rounding by adding a small number computed from the sign bit of the dividend. This works for any x with all shift values from 1 to 30.

If the shift is 1 (i.e., you are dividing by 2) then the >> 31 can be removed in the first formula to give this very tidy snippet:

int result = (x + (x >>> 31)) >> 1;

I have found these techniques to be faster even when the shift is non-constant, but obviously they benefit the most if the shift is constant. Note: For long x instead of int, change 31 and 32 respectively to 63 and 64.

Examining the generated machine code shows that (unsurprisingly) the HotSpot Server VM can do this optimization automatically when the shift is constant, but (also unsurprisingly) the HotSpot Client VM is too stupid to.