programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# right shifting?

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

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

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.

Marshal
Posts: 57437
175
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.

Java Cowboy
Sheriff
Posts: 16079
88
• 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.

 Create symphonies in seed and soil. For this tiny ad: The WEB SERVICES and JAX-RS Course https://coderanch.com/t/690789/WEB-SERVICES-JAX-RS