36

Possible Duplicates:
Is shifting bits faster than multiplying and dividing in Java? .NET?
Quick Java Optimization Question

Many years ago in college, I learned that bit-shifting right by one accomplishes the same thing as dividing by two, but is generally significantly faster. I'm not sure how Java has come along in that regards since the 9-10 years ago I learned about that. Does the Java compiler automatically converts a divide-by-two into a bit-shift operation, or should I manually perform the bit-shift operation in the code myself?

Community
  • 1
  • 1
Matt Huggins
  • 81,398
  • 36
  • 149
  • 218
  • 1
    http://stackoverflow.com/questions/1514949/quick-java-optimization-question It addresses multiplication by two, but the answers are applicable. – robert_x44 Nov 01 '10 at 20:17
  • 1
    In general, if operation A accomplishes *exactly* the same thing as operation B and does it faster, somewhere along the line B will probably be optimized into A. The problem is when there are border-case differences such that one can't be optimized into the other. In those cases you have to 1) evaluate if the difference in performance actually matters (no premature optimization!), 2) account for the border cases (program around them or prove they won't be hit, and 3) determine whether the gains exist and justify the decrease in readibility. – Mark Peters Nov 01 '10 at 20:29
  • 7
    I'm deeply sadened by the spectrum of answers this question got. First, dividing by two and shifting right by one will not yield the same result for negative numbers in all cases. Second, where the shifted result is sufficent, its roughly 10 to 20 times faster than dividing. Third, the compiler will not optimize this because in any non-trivial case it will be unable to prove that the shifted operand is not negative. Oh and the answers from the multiplication question do not cover divide, as the situation with optimizers is different xD – Durandal Nov 01 '10 at 21:20
  • 2
    bit-shifting is not the same as division.. Proof: assert ((-3 >> 1) == (-3 /2)) – Nils Pipenbrinck Nov 01 '10 at 21:36
  • @Pipenbrinck - Sorry, I was talking in terms of integers & rounding, but I neglected to clarify. Thanks for pointing that out. – Matt Huggins Nov 01 '10 at 23:30
  • Possible duplicate: http://stackoverflow.com/questions/1168451/is-shifting-bits-faster-than-multiplying-and-dividing-in-java-net – Galactus Nov 01 '10 at 20:21
  • This is one of the optimizations performed by the Proguard tool. So, if you use this tool, you won't need to do that yourself. – Phantômaxx Apr 11 '14 at 10:37
  • You should not see this in code. If you do see this in code and don't know bit shifting well enough, you should probably not work there. It'll be used a LOT in shaders and similar code, where you should be VERY familiar with low level techniques already. In other types of code, such as business logic, it should rarely be needed. – Killroy Aug 18 '15 at 15:48
  • [Which is better option to use for dividing an integer number by 2?](https://stackoverflow.com/q/10681375/995714) – phuclv Jun 07 '17 at 07:44
  • I know is old question, but: About positive integers, If you are adding numbers to find the middle, even it is not clear code, this approach is safe against Numeric Overflow: int middle = (Integer.MAX_VALUE + Integer.MAX_VALUE) >>> 1; returns the MAX_VALUE, while if you do with / 2: int middle = (Integer.MAX_VALUE + Integer.MAX_VALUE) /2; causes overflow and returns -1. Just something to keep in mind. – Brother Sep 27 '19 at 09:29

3 Answers3

71

Unless you're working in a shop and a codebase where bit-shifting is common then, IMHO, you're risking obfuscation. Yes, the expressions may be logically equivalent but:

  • A n00b might get confused by the alternate syntax
  • An old guy who hasn't had to do any bit-shifting since college, like myself, might get confused
  • If you bit shift and feel the need to comment on what you just did then you're definitely off. Simple division is self-documenting and would be clear to anyone who's familiar with elementary math
  • You're not going to outsmart a compiler for optimization on something that simple so don't bother trying
  • As good coding practice it's better to make your code simple/vanilla rather than clever(er)

All this is relative and, again, really depends on your shop's standards. If your colleagues love to bit-shift, then by all means go forth and bit-shift.

Paul Sasik
  • 79,492
  • 20
  • 149
  • 189
  • 35
    Its in the eye of the beholder. Why is `x * 2` less obfuscated than `x << 1`? Isn't `x << 1` clearly meaning `x * 2` ? It's like saying hey `x + 1` is clearer than `1 + x`. – Pacerier Jan 31 '12 at 14:58
  • 11
    Many programmers, especially junior devs, aren't familiar with bitshifts, or won't immediately recognize the intent. This is basically a usability argument for programmers that may work on the code after you. – cacois Oct 24 '12 at 22:15
  • You can always comment code; and why assume the context in which this is being considered when none is given? – Chris2048 Aug 08 '13 at 21:48
  • 6
    @Chris2048: If you need to comment code because your choice of operator may initially confuse another programmer then, IMO, you have just made the code more difficult to comprehend. – Paul Sasik Aug 08 '13 at 22:00
  • 7
    @Pacerier: `x << 1` being equivalent to `x * 2` will only be clear to programmers who need to or want to twiddle with bits somewhat ferquently. I haven't had to bit-shift anything since my sophomore year in college, many years ago, and seeing bit-shifting in place of a simple division or multiplication symbol in code would only provoke a WTF? – Paul Sasik Aug 08 '13 at 22:04
  • 22
    To put @PaulSasik's statement another way, it's an issue of abstractions. Yes, the number is represented internally in binary, but when the programmer has a number `x` and wants to divide it by a number that just happens to be `2` (because we like the half things), the programmer is in the abstraction layer of decimal numbers. Shifting in this layer is to multiply by `10`. To see `x >> 1` as `x / 2` is to go down an abstraction layer to the binary representation. Bit shifting makes "sense" when the programmer is already in the binary abstraction layer, dealing with binary numbers. – Dandre Allison Jan 10 '14 at 23:19
  • Put bitshift in the code. That way all people will get to learn about the technique. :) – sjas Aug 24 '14 at 16:02
  • Yes, put bitshift in the code. That way your team will learn a valuable lesson when the system grows and then fails for bizarre reasons caused from not understanding the difference between multiplying by 2 and bitshifting. – John Churchill Dec 17 '18 at 18:11
26

Yes, this is the very first thing that anyone attempting to do compiler optimizations will do (and has done for at least 5 decades), it most certainly is done by the Java JIT compiler, and you'd probably have a very hard time finding any compiler that doesn't do it.

And even if they didn't, it would still be a premature micro-optimization that should be avoided in favor of having the code be clearer.

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • 3
    this should be the answer, instead of actually answering the question if java does it or not, people dance around if its good practice or not... – vach Nov 25 '16 at 04:24
  • "Most certainly?" Have you perf tested it? Then you will know that it doesn't, and shouldn't. Because they are not the same. – John Churchill Dec 17 '18 at 18:03
  • @JohnChurchill: I have and it does. `x * 120` gets compiled to `mov eax,78h; imul edx,eax` but `x * 128` gets compiled to `shl edx,7h` - what exactly gave you the idea that it would not be the same? – Michael Borgwardt Dec 18 '18 at 10:39
12

The division routine for your CPU will handle this. There is no need for you to do it.

This is known as a premature optimization.

Malfist
  • 31,179
  • 61
  • 182
  • 269
  • 20
    Early optimization != premature optimization. Yes *most* of the time when someone wants to start bit twiddling it probably is an example of premature optimization, but that is not always the case. I've personally seen instances where I've gotten noticeably better results bit twiddling because I had information the compiler didn't. I hate that everyone always just starts shouting "premature optimization!!!" anytime something like this is brought up. – Michael McGowan Nov 01 '10 at 20:30
  • 1
    I'd agree with that, but by and large it would be a premature optimization. And often optimizations aren't so much as finding something that is slightly faster and using it instead, rather, it's finding a new way to solve a problem that requires less work. – Malfist Nov 01 '10 at 20:35
  • 4
    The division 'routine' of your CPU is infact an instruction, and it will always be around 20 times slower than a bit-shift. The 'compiler' may replace a division with a shift, but that's it. – Nils Pipenbrinck Nov 01 '10 at 21:32
  • @Nils Pipenbrinck, Where do you get the 20x slower from? I would assume, at best it would depend on the architecture. – Malfist Nov 03 '10 at 13:14
  • 5
    A shift will be a single cycle instruction on almost all architectures while the best CPUs can only do 2 bits of division per cycle (newest intel core RADIX-16 divider). for 32 bit that makes 1 cycle for shift vs 16 cycles for a division in the best case. Add in the startup cost and pipeline stalls and you end up with a factor of around 20. – Nils Pipenbrinck Nov 04 '10 at 09:48
  • It seems like an affirmative answer to the 80% case; the other 20% should be considered too. – Chris2048 Aug 08 '13 at 21:51
  • 3
    OK, granted this is 3 years late, but a simple time comparison of division vs bit-shift shows bit shift @ ~5x faster at 1 billion calculations. Not sure how many calculations you would need to hit that x20 mark, but I'm guessing you would still be waiting for it to complete :) – jason todd Oct 02 '13 at 20:24