= Solution
Write $H=2^{n-1}$ and $U=H-1$. The operands occupy the <integer> points of the square $[-H,U]^2$. The exact sum is representable precisely when
$$
\boxed{-H\leq x+y\leq U.}
$$
The upper boundary is $y=U-x$, and the lower boundary is $y=-H-x$. Within the operand square, the closed band between these lines is representable. The triangle below the lower line has negative overflow, and the triangle above the upper line has positive overflow. The boundary lines themselves are included.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2003/computing-prelims-2003-overflow.png]
{title=Exact addition and subtraction ranges for four-bit two's complement operands}
Consequently overflow occurs exactly when $x+y<-H$ or $x+y>U$. Negative overflow requires two negative operands; positive overflow requires two nonnegative operands. Same-sign operands alone are not sufficient: their exact sum must cross a range endpoint. Opposite-sign operands never overflow on addition. In terms of the stored wrapped result, addition overflows exactly when the operands have equal sign <bits> and the result has the opposite sign <bit>.
The illustration uses $n=4$, so $H=8$ and $U=7$, and marks every permissible operand pair. The general region follows from the same two inequalities for arbitrary $n\geq1$.
Back to article page
