1

For instance:

Dividing by 2

int med = lo + (hi - lo) / 2;

Bitwise right shift

int med = lo + hi >>> 1;

I'm wondering, is there any particular advantage to using a bitwise operation instead of dividing by 2? Does using a bitwise operation offer a more efficient or reliable calculation?

I'm mostly wondering because java.util.Arrays uses the bitwise shift when performing a binary search.

user3670994
  • 19
  • 2
  • 1
    Note, your second expression assumes that `lo + hi` will never be negative for any reason other than overflow. If `lo` is -2 and `hi` is 0, `med` will be equal to `Integer.MAX_VALUE` rather than -1. – cHao May 24 '14 at 05:41
  • 1
    @cHao Yeah, good call. In this case it would only be caused by overflow. I was mostly wondering, and I updated my OP to reflect this, because `java.util.Arrays` uses the bitwise operation when performing a binary search. – user3670994 May 24 '14 at 06:07

3 Answers3

4

Not likely

Your compiler has an optimizer in it that knows how to multiply as quickly as your target processor architecture is capable. So it is possible that the compiler already does this optimizations.

Often a multiply or divide can be decomposed to a series of shifts and adds, and if that series of operations will be faster than the maultiply or divide, the compiler will use it.

coder hacker
  • 4,819
  • 1
  • 25
  • 50
  • 2
    For Java (at least in Oracle's version), it'd be the JITter that does this. The compiler proper does very little if any optimization. – cHao May 24 '14 at 05:24
3

Shifting bits left and right is apparently faster than multiplication and division operations on most (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.

More info on this post :

Is shifting bits faster than multiplying and dividing in Java? .NET?

Community
  • 1
  • 1
mad_mask
  • 776
  • 2
  • 10
  • 31
1

No compiler would be so stupid as to actually emit a full division for it. But that doesn't mean there's no difference. A signed division by 2 is more complicated than a right shift, you'd have to do something like this:

mov edi, eax
shr eax, 31
add eax, edi
sar eax, 1

Unless you can prove that the number you're dividing by 2 is non-negative. That would require proving hi >= lo. In a binary search, that might just be feasible (if there's an if (hi < lo) return false; or something like that before calculating the middle).

Even then the division way still has 3 operations versus 2 of the shift version. Maybe a sufficiently smart JIT compiler can see through that as well, but we're asking more and more of it now.

The old interpreters of the beginning days of Java certainly wouldn't have done any of this, and neither would the first JIT compilers.

So there's a small advantage to writing hi + lo >>> 1, and there are really no downsides. So why wouldn't they use it?

harold
  • 61,398
  • 6
  • 86
  • 164