1

While reading Java Source code for Collections.reverse method, Right Shift operator is used for finding middle.

......
            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--) // Right Shift 
                swap(list, i, j);
.....

Same can be done by using traditional divide by 2 approach.

I explored on stack Right Shift to perform division and find that its better to use division operator and not Right Shift.

UPDATE : But then why java guys used Right Shift and not division ?

So which approach is better to use and Why ?

Community
  • 1
  • 1
Prateek
  • 12,014
  • 12
  • 60
  • 81
  • 1
    `I explored on stack Right Shift to perform division and find that its better to use division operator and not Right Shift.`... erm _hello_? – Hungry Blue Dev May 08 '14 at 06:18
  • 1
    So you had already found a duplicate before you posted this? Not believing the existing answers is not a reason to ask a duplicate question. What makes you think that the answers on this instance of the question will be any more believable than last time? – Dawood ibn Kareem May 08 '14 at 06:20
  • I have already mentioned that link.So obviously i m asking something not answered der. – Prateek May 08 '14 at 06:21
  • 1
    Then you'd better clarify what it is that you feel is new about your question, or it's going to get closed very quickly and probably deleted. – Dawood ibn Kareem May 08 '14 at 06:21
  • I have mentioned it in my update – Prateek May 08 '14 at 06:24
  • May I assume that you're aware that `/ 2` and `>> 1` give different results for negative numbers? – Dawood ibn Kareem May 08 '14 at 20:45

4 Answers4

5

Signed division by 2 and right shift by 1 are not completely equivalent. Division by 2 rounds towards zero, even for negative numbers. Right shift by 1 rounds downwards, which means -1 >> 1 is -1 (whereas -1 / 2 is zero).

Concretely, that means that if the JIT compiler can not (or does not) prove that a number can not be negative (if you had posted the full code, I might have been able to check that), it has to do a something more complicated than merely a right shift - something like this: (divides eax by 2 and clobbers edi, based on what GCC output)

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

If you had used a right shift by 1, it would just be something like

sar eax, 1

It's not a big difference, but it is a difference, so the "it doesn't make any difference"-crowd can go home now. Ok it's only on the loop initialization, so it doesn't have a serious impact on performance, but let's not forget that this is library code - different guidelines apply. Specifically, readability is less emphasized, and the guideline "don't waste performance unless you absolutely must" is more emphasized. Under the circumstances, there is no good reason to write size / 2 there, all that would do is make the performance a tiny bit worse. There is no upside.

Also, I find this readability thing a little silly in this case. If someone really doesn't know what size >> 1 does, that's their problem - it's just one of the basic operators, not even some convoluted combination of operators, if you can't read it then you don't know Java.

But feel free to use size / 2 in your own code. The takeaway from this answer shouldn't be "division by 2 is bad", but rather, "library code shouldn't sacrifice performance for readability".

harold
  • 61,398
  • 6
  • 86
  • 164
  • 1
    +1 for rant against so called "readability", which in this case means "I have no clue about bits, bytes, words and 2's-complement representation of int, and so I don't understand the code." – Ingo May 08 '14 at 09:50
3

It's always better to use the more readable option, unless there is a pressing need for speed.

Go with the clear, obvious division and then if you find yourself needing to optimize later you can change to the right shift and comment clearly.

Evan Knowles
  • 7,426
  • 2
  • 37
  • 71
  • 3
    +1: I strongly doubt that shift is noticeably faster anyway. It seems like an easy optimization to perform for the JVM, so if it is faster to shift it is probably optimized automatically. – Keppil May 08 '14 at 06:19
  • It is not an easy optimization, the JIT would have to prove that the divident is not negative. See @harold's answer. – Ingo May 08 '14 at 09:52
0

In practice it doesn't matter, but a division makes the intent cleaner, and I can only imagine that one would attempt a bitshift for "performance reasons". But it's 2014 and you're not writing x86 assembly by hand, so trying to optimize code like this is a waste of time.

Kayaman
  • 72,141
  • 5
  • 83
  • 121
0

The right shift operator is fast as compared to the division operator. As you know all the data is stored and processed in the binary format. The right shift works directly on the binary format and hence is fast and optimal. The division works on integer numbers and hence is slow and not optimal. But since the processor speed now is fairly good and it doesnt really make a difference that you use which ever operator, the choice is really yours. If you think that your app already takes too much of processor speed and you really feel a need to lessen the load, you can use right shift. For light weight applications, division operator is suitable.

Aradhna
  • 973
  • 10
  • 20
  • _fast_: how? Give us some proof. – Hungry Blue Dev May 08 '14 at 06:25
  • When you store some data, it is first converted into binary format and then stored. When you again retrieve that data to change, the binary form is converted into the desired form and then the change is applied. For right shift, the second change from binary format is not needed and hence it is fast as it lessens the processor load. – Aradhna May 08 '14 at 06:28
  • Both operations are instrumented at Bytecode level by an independent unique instruction (`iushr` and `iadd`). Unless you actually know how how the bytecodes are implemented you will have a hard time proving this answer. – Edwin Dalorzo May 08 '14 at 06:28
  • Just read this article. https://community.oracle.com/message/8717135 – Aradhna May 08 '14 at 06:36