Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 10 / a

An $n$-bit two's complement word $b_{n-1}\cdots b_1{b}_0$ represents the integerThe leading bit has negative weight. Words beginning with zero encode the nonnegative values; words beginning with one encode the negative values. Equivalently, interpret the whole word as unsigned and subtract $2^n$ when its leading bit is one. For example, the four-bit words 0111, 1000, and 1111 encode $7$, $-8$, and $-1$ respectively. The range is asymmetric: the most negative value has no positive counterpart in the same number of bits.

For a nonzero representable magnitude, complementing all bits and adding one obtains its negative modulo $2^n$. Fixed-width addition can therefore use the same low-order binary numeral system addition circuitry for signed and unsigned operands; interpreting the result as signed requires detecting integer overflow.

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 whenThe 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.

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\ge 1$.

For the exact difference, the representability condition becomesWithin the same operand square $[-H,U{]}^2$, the closed diagonal band between $y=x-U$ and $y=x+H$ is representable. Above the upper line, $x-y<-H$ gives negative overflow; below the lower line, $x-y>U$ gives positive overflow. The right-hand panel of the figure shows these regions, including their representable boundary points.

Positive overflow can occur only when $x\ge 0$ and $y<0$; negative overflow can occur only when $x<0$ and $y\ge 0$. The corresponding exact inequalities are still required: operands with different signs do not always overflow. Same-sign subtraction is always representable. In sign-bit terms, subtraction overflows exactly when the operands have different signs and the wrapped result's sign differs from that of $x$.

One must test subtraction directly or use its correct overflow rule: forming -y in the same $n$ bits fails at $y=-H$, even though some differences with that operand are representable. For example $(-H)-(-H)=0$ is valid.