Comparison is an operator that returns a value that is true or false. Although we are familiar with 6 comparison operators, the less-than operator alone is sufficient to “span” the other operators. The equivalence is listed as follows:
However, even though just “less than” is enough to span all the other comparison operators, knowing whether a binary number is representing a value that is less than that of another binary number is not a straight forward matter.
Unsigned comparison is a little bit easier. Let us first establish some ground rules:
These two are conclusive on their own, even if we are comparing multi-bit numbers. Let us consider the case of comparing \(x\) to \(y\), and we are only interested to know whether the unsigned value represented by \(x\) is less than the unsigned value represented by \(y\).
For notation purposes, let \(x_i\) represent the \(i\)th bit of \(x\). Likewise for \(y\).
We know that \(x_i\) represents the quantity (presence) of \(2^i\) of the value represented by \(x\) as a binary number. We also know that \(2^n > \sum _{i=0}^{n-1}2^i\). Or, do we?
How do we prove \(2^n > \sum _{i=0}^{n-1}2^i\)? Just because it works for all the concrete examples that we can come up with is not sufficient. Let’s see if we can make a rigorous proof. Because the power of 2 appear on both sides, this suggests that proof by induction may be a good idea.
The base case is when \(n=1\). When \(n=1\), we can spell out the comparison as \(2^1 = 2 > 1 = 2^0\). Now, we can prove the induction step. The induction assumption is that \(2^k > \sum _{i=0}^{k-1} 2^i\) for some \(k>1\). Our job is to show that \(2^{k+1} > \sum _{i=0}^{k} 2^i\).
This is how the proof goes:
\begin {align*} 2^{k+1} & > \sum _{i=0}^{k} 2^i \\ 2^k + 2^k & > \sum _{i=0}^{k} 2^i \\ 2^k & > \sum _{i=0}^{k-1} 2^i \\ \end {align*}
But this is just what the induction assumption is assuming! We have the proof done now!
Now we want to prove that in an \(m\)-bit subtraction, \(u_m(x)<u_m(y) \Leftrightarrow t_m = 1\), assuming \(t_0 = 0\). In this subtraction, \(x\) is the \(m\)-bit minuend, and \(y\) is the \(m\)-bit subtrahend. \(u_m(n)\) is the \(m\)-bit unsigned value interpreted from the bit pattern n, \(u_m(n)=\sum _{i=0}^{m-1}n_i2^i\).
Let us use proof-by-induction again. The base case is when \(m=1\). Recall in the subtraction module that \(t_{i+1}=b(x_i,y_i)+b(q_i,k_i)\), for binary subtraction \(b(x,y)=!xy\), and \(q_i=x_i \oplus y_i\).
The base is proven by showing that \(t_1=!x_0y_0 + (x_0 \oplus y_0)r_0\). Since \(k_0=0\), \(t_1 = !x_0y_0\). This means that \(t_1=1 \Leftrightarrow (x_0=u_1(x)=0 \wedge y_0=u_1(y)=1) \Leftrightarrow u_1(x)<u_1(y)\).
The induction step assumes the theorem is true for bit widths up to \(m-1\). In other words, we assume that for any \(m-1\) bit binary subtraction, \(t_{m-1}=1 \Leftrightarrow u_{m-1}(x)<u_{m-1}(y)\).
Given this assumption, let us consider \(t_m\) in an \(m\)-bit subtraction. We know that \(t_m = b(x_{m-1},y_{m-1}) + b(q_{m-1},t_{m-1})\). There are two cases to consider.
This concludes the proof!
In a signed interpretation, the value represented by a bit pattern is not exactly the sum of powers of 2 like with an “unsigned” interpretation. This introduces a bit of problem.
First of all, the borrow bit \(t_i\) is no longer of any use in terms of the determination of whether the minuend is less than the subtrahend.
Recall that two-s complement is merely a method to compute the arithmetic negation of the binary representation of a signed value. Given \(m\) bits, the actual arithmetic negation method is \(2^m-x\).
The way values are assigned to an \(m\)-bit binary representation can be summarized as follows:
\begin {align*} v(x) & = (x_{m-1}) ? (-(2^m - \sum _{i=0}^{m-1}x_i2^i)) : (\sum _{i=0}^{m-1}x_i2^i) \\ & = (x_{m-1}) ? ((\sum _{i=0}^{m-1}x_i2^i)-2^m) : (\sum _{i=0}^{m-1}x_i2^i) \\ & = (x_{m-1}) ? ((\sum _{i=0}^{m-2}x_i2^i)-(2^m-x_{m-1}2^{m-1})) : (\sum _{i=0}^{m-2}x_i2^i) \\ & = (x_{m-1}) ? ((\sum _{i=0}^{m-2}x_i2^i)-(x_{m-1}2^{m-1})) : (\sum _{i=0}^{m-2}x_i2^i-x_{m-1}2^{m-1}) \\ & = (\sum _{i=0}^{m-2}x_i2^i)-x_{m-1}2^{m-1} \end {align*}
This is why bit \(m-1\) (the most significant bit) is also called the sign bit because its value affects the sign of the value represented by the bit pattern.
Comparison of signed values is relatively straightforward because of the following derivation:
\begin {align*} x & < y \Leftrightarrow \\ x-y & < y - y \Leftrightarrow \\ x-y & < 0 \end {align*}
Defining \(d=x-y\) as the difference, we should be able to use the sign bit of the difference, \(d_{m-1}\) to indicate whether \(x\) is less than \(y\). However, the boundary cases are tricky.
There are two ways to cross the boundary. A negative value minus a positive value can become “positive” because the result crosses the \(\pm \) boundary. A positive number minus a negative value can cross the same boundary, but in the other direction. Let us example some 4-bit examples.
When the result of a subtraction exceeds the range of a signed number, the sign of the difference makes no sense. But this also means we can no longer rely on the sign of the difference alone to indicate whether the minuend is smaller than the subtrahend.
The overflow flag/condition is defined as the sign of the result being wrong. In the case of 4-bit binary numbers, \(5-(-4)\) results in overflow being true. In the subtraction \(x-y=d\), the two ways to overflow are
Of course, we are determining whether the minuend \(x\), subtrahend \(y\) or difference \(d\) is less than 0 or not purely based on their sign flags.
The overflow flag is usually denoted by “O” (upper case o) or “V”. The equation to define it for subtraction needs to capture the two cases when the value of difference exceeds what can be represented.
\(O=x_{m-1}!y_{m-1}!d_{m-1}+!x_{m-1}y_{m-1}d_{m-1}\)
Again, \(m\) is the number of bits of each number. Using this notation, we can also design the sign flag/condition that reflects the sign of the result: \(S=d_{m-1}\). It is merely the most significant bit of the result.
Using the S and O flags, we have enough information to determine whether the minuend is less than the subtrahend when both represent signed values in a subtraction.
Let us consider the four combinations of the S and O flags:
As an exercise, it is helpful to think of examples for all four cases. The analysis does indicate that whenever \(S \ne O\), the minuend is less than the subtrahend. Whenever \(S = O\), the minuend is not less than the subtrahend.
For our convenience, we define a new flag \(L=S!O + !SO\) so that we can use this one flag to indicate in a subtraction of signed values whether the minuend is less than the subtrahend.
Now that we can see how the subtraction of two signed binary numbers can overflow the result, what about addition? Can the addition of two signed binary numbers overflow the sum? If so, how should the overflow flag O be defined?