StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In short, <code>(high + low) >>> 1</code> is a trick that uses the unused sign-bit to perform a correct average of non-negative numbers.</p> <hr> <p>Under the assumption that <code>high</code> and <code>low</code> are both non-negative, we know for sure that the upper-most bit (the sign-bit) is zero.</p> <p>So both <code>high</code> and <code>low</code> are in fact 31-bit integers.</p> <pre><code>high = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 low = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 </code></pre> <p>When you add them together they may "spill" over into the top-bit.</p> <pre><code>high + low = 1000 0000 0000 0000 0000 0000 0000 0000 = 2147483648 as unsigned 32-bit integer = -2147483648 as signed 32-bit integer (high + low) / 2 = 1100 0000 0000 0000 0000 0000 0000 0000 = -1073741824 (high + low) >>> 1 = 0100 0000 0000 0000 0000 0000 0000 0000 = 1073741824 </code></pre> <ul> <li><p>As a signed 32-bit integer, it is overflow and flips negative. Therefore <code>(high + low) / 2</code> is wrong because <code>high + low</code> could be negative.</p></li> <li><p>As unsigned 32-bit integers, the sum is correct. All that's needed is to divide it by 2.</p></li> </ul> <p>Of course Java doesn't support unsigned integers, so the best thing we have to divide by 2 (as an unsigned integer) is the logical right-shift <code>>>></code>.</p> <p>In languages with unsigned integers (such as C and C++), it gets trickier since your input can be full 32-bit integers. One solution is: <code>low + ((high - low) / 2)</code></p> <hr> <p>Finally to enumerate the differences between <code>>>></code>, <code>>></code>, and <code>/</code>:</p> <ul> <li><code>>>></code> is logical right-shift. It fills the upper bits with zero.</li> <li><code>>></code> is arithmetic right-shift. It fills the upper its with copies of the original top bit.</li> <li><code>/</code> is division.</li> </ul> <p>Mathematically:</p> <ul> <li><code>x >>> 1</code> treats <code>x</code> as an unsigned integer and divides it by two. It rounds down.</li> <li><code>x >> 1</code> treats <code>x</code> as a signed integer and divides it by two. It rounds towards negative infinity.</li> <li><code>x / 2</code> treats <code>x</code> as a signed integer and divides it by two. It rounds towards zero.</li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload