8

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?

Community
  • 1
  • 1
Cratylus
  • 52,998
  • 69
  • 209
  • 339

4 Answers4

6

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.

Sergey Kalinichenko
  • 714,442
  • 84
  • 1,110
  • 1,523
  • So it is not possible to write bug free code without shift operator for subtle issues such as this? – Cratylus Feb 12 '12 at 09:45
  • @user384706 Of course you can: a simple ternary operator here and there could help you do the trick. However, the efficiency is going to suffer. – Sergey Kalinichenko Feb 12 '12 at 09:49
  • Would it be possible to show an example of this?I would be interested in knowing – Cratylus Feb 12 '12 at 10:04
  • @user384706 Well it's pretty easy. See [this](http://stackoverflow.com/questions/9071797/ruby-unsigned-right-shift/9072121#9072121) for an example on how to write a unsigned shift operator if you only have a signed one. – Voo Feb 12 '12 at 13:05
  • @Voo:The post you linked to does not use the `/` operator – Cratylus Feb 12 '12 at 15:37
  • 1
    @user384706 Same principle - save sign, do unsigned/signed computation, fix the result. Can be done with basically any computation. – Voo Feb 12 '12 at 18:23
  • @user384706 you can do this: `(n<0) ? (((n&0x7FFFFFFF)/2)|0x40000000) : (n/2)`. – Sergey Kalinichenko Feb 12 '12 at 18:35
  • @dasblinkenlight:I thought you said `it is not possible to emulate a >>> 1 with a /= 2` – Cratylus Feb 12 '12 at 21:19
  • 1
    @user384706 I meant it wasn't possible with `n/2` *alone*. I emulated it with a combination of `n/2`, a conditional, a bitwise `AND`, and a bitwise `OR`, for a potentially significant loss in performance. – Sergey Kalinichenko Feb 12 '12 at 22:10
5

Apart from shift being faster than division on most systems. The >>> performs an unsigned operation, which division does not. e.g. if you want the mid point of two values, you need to use >>> to avoid an overflow. (See Arrays.binarySearch for similar code)

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
  • I was wondering why do you mention performance in your first sentence.Will not JVM optimise it anyway?This is what I understand from the other SO thread I mention in OP – Cratylus Feb 12 '12 at 14:47
  • 1
    Division isn't equivalent to shifting if the inputs are negative, and the JVM can't always prove that the inputs are nonnegative, in which case it has to take the hit of division. – Louis Wasserman Feb 12 '12 at 15:36
  • @LouisWasserman:So you saying that we must always use shift operators because JVM will not always optimize as we expect?In the SO thread I linked to, this was not mentioned I believe – Cratylus Feb 12 '12 at 15:46
  • I figure the JVM is probably smart about it in cases where the input is known to be nonnegative, but (-1/2) == 0 and (-1 >> 1) == -1 (and -1 >>> 1 == Integer.MAX_VALUE), so it can't just replace division-by-2 with right-shift. – Louis Wasserman Feb 12 '12 at 15:55
  • 1
    If you divide by `n` where `n` is always a power of two, it won't know this. If you always shift by `m` its clear what you are doing. If you divide by `2` (a constant) it will do the same as `>>` but not `>>>` because there is no unsigned division by 2 in Java. – Peter Lawrey Feb 12 '12 at 17:27
3

Some valid reasons to prefer shifting in Java:

  • If there is a chance that you may be running in a non-optimised environment and you can't guarantee that the JIT compiler will make the necessary optimisation for you. This is probably rare nowadays, but could still happen in some circumstances.
  • If you are genuinely doing bit manipulations rather than numerical operations - it is more clear in the source code to use shifts directly
  • If you want unsigned operations (for example you can easily do unsigned shifts, but not unsigned divides)
mikera
  • 105,238
  • 25
  • 256
  • 415
2

It is more a matter of taste. Some people are so used to binary operations that they are more native to them (I personally also use such in code I am writing for myself). However from performance point of view the two behave the same (the optimization happens compile-time so the use of shifts will improve the compile time, but with minor fraction and you can neglect that).

EDIT And as it happens often there is something new I learn from every answer I give: consider this. It proves why division by two can not always be optimized to shifting. So my above comment is almost completely wrong, as long as java does not have unsigned types.

Boris Strandjev
  • 46,145
  • 15
  • 108
  • 135
  • 1
    More generally: The JIT in java can only replace divison by a power of 2 with shifts if it can guarantee that the numbers are positive. If not, we need a more complex routine (which basically boils down to 3 shifts and an add for the branch free version, or a branch and add + shift) – Voo Feb 12 '12 at 13:09