This week's book giveaway is in the JavaScript forum.
We're giving away four copies of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js and have Paul Jensen on-line!
See this thread for details.
Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

right shifting?  RSS feed

 
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
Posts: 55333
157
  • 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
Sheriff
Posts: 16007
87
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.
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!