Definition 1.4.1. Signed interpretation of bit strings.
\begin{equation*}
\bsintp\cdot:\Bit^n\to\Int\qquad\bsintp{b_{n-1}\bseqq b{n-2}}\mapsto
-b_{n-1}\cdot 2^{n-1}+\buintp{\bseqq{b}{n-2}}=\buintp b-b_{n-1}2^n
\end{equation*}
Section 1.4 The Integers
Up to now we were only assigning non-negative numbers to bit strings using the function \(\buintp\cdot\text{.}\) However, it would be nice to be able to do meaningful computations on bit strings that represent negative numbers as well. To do this, we need to come up with a new interpretation of bit strings that represents positive and negative numbers.
We have proven (Lemma 1.3.5) that the addition algorithm of Definition 1.3.3 always preserves the values under the unsigned interpretation modulo \(2^n\text{.}\) We have already discussed the role of the carry out of the most significant position to detect overflows in the case of adding or subtracting unsigned numbers. We will see shortly that our addition algorithm also works for signed numbers in a similar way: It preserves the signed interpretation modulo \(2^n\) but has a different criterion for determining an overflow, as the following examples show:
\begin{align*}
\buintp{011} + \buintp{110} = 9 \amp \ne \buintp{011\mathrel{+_3}110} = 1\\
\bsintp{011} + \bsintp{110} = 1 \amp = \bsintp{011\mathrel{+_3}110}\\
\buintp{011} + \buintp{001} = 4 \amp = \buintp{011\mathrel{+_3}001}\\
\bsintp{011} + \bsintp{001} = 4 \amp \ne \bsintp{011\mathrel{+_3}001} = -4
\end{align*}
The next lemma clarifies under which circumstances the lower \(n\) bits of an addition represent the accurate result with respect to the signed interpretation and also gives a condition for the overflow:
Lemma 1.4.3. Signed addition.
\(\bsintp a+\bsintp b=\bsintp{a\baddn b}\) if and only if \(c_n= c_{n-1}\text{.}\)
Proof.
\begin{align*}
\bsintp a+\bsintp b \amp = -(a_{n-1}+b_{n-1})\cdot 2^n+\buintp a+\buintp b \amp \knowl{./knowl/def-arith-sintp.html}{\text{Definition 1.4.1}}\\
\amp = -(a_{n-1}+b_{n-1})\cdot 2^n+\buintp{a+b} \amp \knowl{./knowl/lem-arith-uadd.html}{\text{Lemma 1.3.5}} \\
\amp = -(a_{n-1}+b_{n-1})\cdot 2^n+\buintp{c_ns_{n-1}}2^{n-1}+\buintp{\bseqq s{n-2}} \amp \knowl{./knowl/lem-arith-splitval.html}{\text{Lemma 1.1.2}} \\
\amp = (c_n-a_{n-1}-b_{n-1})\cdot 2^n+s_{n-1}2^{n-1}+\buintp{\bseqq s{n-2}} \amp \knowl{./knowl/lem-arith-splitval.html}{\text{Lemma 1.1.2}} \\
\amp = (c_n+s_{n-1}-a_{n-1}-b_{n-1})\cdot 2^n+\bsintp{\bseq sn} \amp \\
\amp = (c_n+a_{n-1}+b_{n-1}+c_{n-1}-2c_n-a_{n-1}-b_{n-1})\cdot 2^n+\bsintp{a\baddn b} \amp \knowl{./knowl/lem-arith-place.html}{\text{Lemma 1.3.1}} \\
\amp = (c_{n-1}-c_n)\cdot 2^n+\bsintp{a\baddn b} \amp
\end{align*}
Remark 1.4.4. Practical Considerations.
As mentioned before, many processors provide the carry out of the most significant position as the carry flag in a flag register. Additionally, these processors typically provide an overflow bit which is just the xor between the carry into and out of the most significant position as indicated by Lemma 1.4.3.
Checkpoint 1.4.5. Overflow Detection for Signed Subtraction.
Show that overflow detection for signed subtraction is equivalent to Lemma 1.4.3
202404261614
Hint.
Adapt Lemma 1.4.3 accordingly.
Checkpoint 1.4.6. Another Way to Check for Signed Overflows.
Suppose your ALU does not provide you with an overflow bit and suppose you do not have access to \(c_{n-1}\text{.}\) So you cannot use Lemma 1.4.3 to compute the overflow bit. Explore how you can compute the overflow bit from the most significant bits of the added numbers, of the sum, and maybe from the carry bit. Come up with adequate boolean expressions that compute the overflow bit from these components.
202404261614
Hint.
Answer.
Use the value table from Lemma 1.3.1
\begin{equation*}
v=(a_{n-1}\band b_{n-1}\band c_{n-1})\bor(\bneg a_{n-1}\band\bneg b_{n-1}\band\bneg c_{n-1})
\end{equation*}
or alternatively
\begin{equation*}
v=(a_{n-1}\band b_{n-1}\band\bneg s_{n-1})\bor(\bneg a_{n-1}\band\bneg b_{n-1}\band s_{n-1})
\end{equation*}
Remark 1.4.7.
Not every operation gives meaningful results on signed and unsigned alike. Consider the less-than operation \(a\lt b\) that yields 1 if \(a\lt b\) and 0 otherwise. For example:
\begin{equation*}
\buintp{001}=1\lt 6=\buintp{110}\quad\text{but}\quad\bsintp{001}=1\not\lt -2=\bsintp{110}
\end{equation*}
So, when performing a comparison on two bit strings, one has to decide if the bit strings are to be interpreted as signed or unsigned numbers. Consequently, modern microprocessors have two operations for comparing integers. On MIPS, which we will discuss in the next section, there is
slt which interprets the bit strings as signed integers and sltu which interprets them as unsigned integers. Remark 1.4.8.
Being signed or unsigned is not a property of the bit string itself but how you interpret it. A binary operation on bit strings just produces another bit string. It may, however, be sound with respect to the signed or the unsigned interpretation (comparison) or with respect to both (addition).
Sign and Zero Extension.
It happens frequently that we want to convert a bit string of length \(m\) into a longer bit string of length \(n\) so that the longer bit string represents the same number as the shorter one.
In such a situation it is important how we want to interpret the bit string: as a signed or an unsigned number because for either case the conversion is different. Converting a shorter to longer bit sequence such that their value stays the same under the unsigned interpretation is called zero extension where as sign extension preserves their value under the signed interpretation.
\begin{equation*}
\begin{array}{rrr}
b \amp \bsintp{b} \amp \buintp{b} \\
\hline
0000 \amp 0 \amp 0 \\
\vdots\amp \vdots \amp \vdots \\
0111 \amp 7 \amp 7 \\
1000 \amp -8 \amp 8 \\
\vdots\amp \vdots \amp \vdots \\
1111 \amp -1 \amp 15 \\
\end{array}
\end{equation*}
\begin{equation*}
\begin{array}{rrr}
b \amp \bsintp{b} \amp \buintp{b} \\
\hline
000 \amp 0 \amp 0 \\
001 \amp 1 \amp 1 \\
010 \amp 2 \amp 2 \\
011 \amp 3 \amp 3 \\
100 \amp -4 \amp 4 \\
101 \amp -3 \amp 5 \\
110 \amp -2 \amp 6 \\
111 \amp -1 \amp 7 \\
\end{array}
\end{equation*}
\begin{equation*}
\begin{array}{rrr}
b \amp \bsintp{b} \amp \buintp{b} \\
\hline
00 \amp 0 \amp 0 \\
01 \amp 1 \amp 1 \\
10 \amp -2 \amp 2 \\
11 \amp -1 \amp 3 \\
\end{array}
\end{equation*}
Figure 1.4.9 shows all bit strings of lengths 4, 3, and 2. Apparently, when the longer bit string preserves the value of the shorter under \(\buintp\cdot\) the bit string is extended with zeros. In the case where the signed value shall be preserved, the most significant bit is replicated: 11 becomes 111 becomes 1111, whereas 01 becomes 001 and 0001. Proving that zero extension preserves the unsigned value is straightforward. The signed case is slightly more interesting:
Lemma 1.4.10.
\(\bsintp{b_{n-1}\bseq bn}=\bsintp{\bseq bn}\)
Proof.
\begin{align*}
\bsintp{b_{n-1}\bseq bn} \amp = \buintp{\bseq bn}-b_{n-1}\cdot2^n \amp \knowl{./knowl/def-arith-sintp.html}{\text{Definition 1.4.1}}\\
\amp = \buintp{\bseqq b{n-2}}+b_{n-1}\cdot 2^{n-1}-b_{n-1}\cdot 2^n \amp \knowl{./knowl/def-arith-uintp.html}{\text{Definition 1.1.1}}\\
\amp = \buintp{\bseqq b{n-2}}-b_{n-1}\cdot 2^{n-1}\amp \knowl{./knowl/def-arith-sintp.html}{\text{Definition 1.4.1}}\\
\amp = \bsintp{b}
\end{align*}
