• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

right shifting?

 
Jon Camilleri
Ranch Hand
Posts: 664
Chrome Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can anyone explain what is happening here?



Taken from Java Source code for 1.6 (Arrays.java)
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Chrome Eclipse IDE
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
IntelliJ IDE Scala Windows
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 50171
79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 15480
43
Android IntelliJ IDE Java Scala Spring
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic