Win a copy of The Java Performance Companion this week in the Performance forum!

# right shifting?

Jon Camilleri
Ranch Hand
Posts: 664
Can anyone explain what is happening here?

Taken from Java Source code for 1.6 (Arrays.java)

Luigi Plinge
Ranch Hand
Posts: 441
• 1
It's shifting all the bits to the right by 1. If you think about it, this is equivalent to dividing by 2 (and discarding the remainder). Shifting by 2 bits would be equivalent to dividing by 4 etc. So the statement just takes the average of low and high.

Jon Camilleri
Ranch Hand
Posts: 664
Luigi Plinge wrote:It's shifting all the bits to the right by 1. If you think about it, this is equivalent to dividing by 2 (and discarding the remainder). Shifting by 2 bits would be equivalent to dividing by 4 etc. So the statement just takes the average of low and high.

So if low is 1 and high is 6 (110 base 2), the resulting value is 3, which is the median value if we had 6 numbers in range.

Source, Median - http://en.wikipedia.org/wiki/Median.

Luigi Plinge
Ranch Hand
Posts: 441
• 1
It's not the median, it's the mean. If you have 3 numbers, e.g. {1,1,10}, the median here is 1 and the mean is 4. All this code is doing is adding two numbers together and dividing by 2 to get the midpoint.

Campbell Ritchie
Sheriff
Posts: 49466
64
You mean if you add 1 and 6 and halve getting 3, then the median value is the value pointed to by no 3. If the array is sorted, of course.

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15369
40
• 1
Luigi explained that shifting right one bit is the same as dividing by 2.

Long ago, this was a common trick to quickly divide a number by 2. The division instruction / on old processors was a relatively slow operation, while shifting one bit to the right was a much faster operation; so writing something like number / 2 was significantly slower than writing number >>> 1. However, this isn't necessarily true anymore on modern microprocessors; and even if it were, then you should let the compiler make micro-optimizations like this.

So, I'd advise you to not use tricks like this in your own code; just write number / 2 when you have to divide a number by two, because it's much clearer, and the compiler will be smart enough to optimize it if necessary.