aspose file tools*
The moose likes Beginning Java and the fly likes right shifting? Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "right shifting?" Watch "right shifting?" New topic
Author

right shifting?

Jon Camilleri
Ranch Hand

Joined: Apr 25, 2008
Posts: 660

Can anyone explain what is happening here?



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


Jon
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

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

Joined: Apr 25, 2008
Posts: 660

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

Joined: Jan 06, 2011
Posts: 441

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

Joined: Oct 13, 2005
Posts: 38357
    
  23
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

Joined: Aug 16, 2005
Posts: 14107
    
  16

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.


Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
 
 
subject: right shifting?