Proving result about 2's complement numbers.

Question

In a book I am reading about computer science I have this result about two complements numbers:

Assume that $a$ and $b$ are two N-bit 2's complement numbers. Then $a<b$ is equivalent to the fact that $a-b$ will either overflow or have a $1$ in the minus position, but not both.

So what I need to prove is: first I assume that $a<b$, then I need to show that $a-b$ will either have overflow or have a $1$ in the minus position but not both.

Then I need to show that if $a-b$ either overflows or has a one in the minus position, but not both, then $a<b$.

Do you see how to solve this?

Answer 1

If $a < b$ then $a-b < 0$. Now there are two cases:$\def\intmin{\mathrm{IntMin}}$ $\def\intmax{\mathrm{IntMax}}$

1. $\quad a-b \geqslant \intmin$
2. $\quad a-b < \intmin$

In case 1, no underflow occurs and $\intmin\leqslant a-b < 0$, thus $a-b$ is the result which must have its highest (sign) bit set.

In case 2, we must add some multiple of $2^n$ in order to get the result back into the range $[\intmin, \intmax]$, where for an $n$-bit signed in 2's complement we have

$$\begin{align} \intmax &= 2^{n-1}-1 \\ \intmin &= -\intmax-1 = -2^{n-1}\\ \end{align}$$

Thus in case 2., we have

$$0 \stackrel{(1)}< a-b+2^n \stackrel{(2)}< \intmin +2^n = 1+\intmax \tag 3$$

The upper bound $(2)$ follows from 2. when we add $2^n$ at both sides.

The lower bound $(1)$ follows because we started with $\intmin \leqslant a,b\leqslant \intmax$:

$$b \leqslant \intmax = \intmin+ \intmax-\intmin \leqslant a+2^n-1 < a+2^n$$

Now $(3)$ means that the case 2. result is $c=a-b+2^n$ and that the sign-bit of $c$ is not set. We had to add $2^n$ once, which means that an underflow occured.