title: Explanation of the safe average of two numbers
body: <p>Whenever I need to average two numbers for an algorithm like binary search, I always do something like this:</p>
  
  <pre><code>int mid = low + ((high - low) / 2);
  </code></pre>
  
  <p>I recently saw another way to do it in <a href="http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html" rel="noreferrer">this post</a>, but I don't understand it. It says you can do this in Java:</p>
  
  <pre><code>int mid = (low + high) &gt;&gt;&gt; 1;
  </code></pre>
  
  <p>or this in C++:</p>
  
  <pre><code>int mid = ((unsigned int)low + (unsigned int)high)) &gt;&gt; 1;
  </code></pre>
  
  <p>The C++ version essentially makes both operands unsigned, so doing a shift results in an arithmetic shift instead of a signed shift. I understand what both these pieces of code are doing, but how does this solve the overflow issue? I thought the whole issue was that the intermediate value <code>high + low</code> could overflow?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Oh, duh. All the answers didn't exactly answer my question, but it was @John Zeringue's answer that made it click. I'll try to explain here.</p>
  
  <p>The issue with <code>(high + low)/2</code> in Java isn't exactly that <code>high + low</code> overflows (it does overflow since the integers are both signed, but all the bits are still there, and no information is lost). The issue with taking the average like this is the division. The division is operating on a signed value, so your result will be negative. Using the shift instead will divide by two but consider the bits instead of the sign (effectively treating it as unsigned).</p>