Menu
I have the following question:
If asked whether to use a shift vs a multiply or divide for example the answer would be, let the JVM optimize.
Example here: is-shifting-bits-faster-than-multiplying
Now I was looking at the jdk source, for example Priority Queue and the code uses only shifting for both multiplication and division (signed and unsigned).
Taking for granted that the post in SO is the valid answer I was wondering why in jdk they prefer to do it by shifting?
Is it some subtle detail unrelated to performance? I am suspecting it must have something to do with over/underflow multiplication and division but I am not sure.
Anyone has an idea? Are subtly overflow issues handled better using shifting? Or it is just a matter of taste?
292
The conventional wisdom is that multiplication and division are much slower than shifting, but the actual story today is more nuanced. For example, it is certainly true that multiplication is a more complex operation to implement in hardware, but it doesn't necessarily always end up slower.
Shifting bits left and right is apparently faster than multiplication and division operations on most, maybe even all, CPUs if you happen to be using a power of 2. However, it can reduce the clarity of code for some readers and some algorithms.
Of course Java can also do multiplication and division. Since most keyboards don't have the times and division symbols you learned in grammar school, Java uses * to mean multiplication and / to mean division.
And so on, we can say the multiply algorithm is faster than left shift algorithm.
I think they do it in this specific example to use the sign bit. Java lacks unsigned types, so it is not possible to emulate a >>> 1 with a /= 2 for numbers that use the most significant bit. Note how the code uses only >>> throughout your example. I am reasonably certain that this is to get full use of the entire bit range.
53
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
