title: Fastest way to take the average of two signed integers in x86 assembly?
body: <p>Suppose we have two register-length<sup>2</sup> signed<sup>1</sup> integers, say <code>a</code> and <code>b</code>.  We want to compute the value <code>(a + b) / 2</code>, either rounded up, down, towards zero, or away from zero, whichever way is easier (i.e. we do not care about the rounding direction).</p>
  <p>The result is another register-length signed integer (it is clear that the average must be within the range of a register-length signed integer).</p>
  <p>What is the fastest way to perform this computation?</p>
  <p>You may choose which registers the two integers will initially be in, and which register the average ends up being in.</p>
  <hr />
  <p>Footnote 1: For unsigned integers, we can do it in two instructions.  This is perhaps the fastest way, although rotate-through-carry is more than 1 uop on Intel CPUs.  But only a couple when the count is only 1.  <a href="https://stackoverflow.com/questions/3816446/how-can-i-safely-average-two-unsigned-ints-in-c/3817136#3817136">An answer</a> on a Q&amp;A about unsigned mean discusses the efficiency.</p>
  <pre><code>add rdi, rsi
  rcr rdi, 1
  </code></pre>
  <p>The two numbers start in <code>rdi</code> and <code>rsi</code>, and the average ends up in <code>rdi</code>.  But for signed numbers, <code>-1 + 3</code> would set CF, and rotate a <code>1</code> into the sign bit.  Not giving the correct answer of <code>+1</code>.</p>
  <p>Footnote 2:  I specified <em>register-length</em> signed integers so that we can't simply sign extend the integers with a <code>movsxd</code> or <code>cdqe</code> instruction.</p>
  <hr />
  <p>The closest I've got towards a solution uses four instructions, one of them an <code>rcr</code> that's 3 uops on Intel, 1 on AMD Zen (<a href="https://uops.info/" rel="noreferrer">https://uops.info/</a>):</p>
  <pre><code>add rdi, rsi
  setge al
  sub al, 1          # CF = !(ge) = !(SF==OF)
  rcr rdi, 1         # shift CF into the top of (a+b)&gt;&gt;1
  </code></pre>
  <p>I think a shorter solution probably lies in combining the middle two instructions in some way, i.e. performing <code>CF ← SF ≠ OF</code>.</p>
  <p>I've seen <a href="https://stackoverflow.com/questions/5697500/take-the-average-of-two-signed-numbers-in-c">this question</a>, but that's not x86-specific and none of the answers seem to compile to something as good as my solution.</p>