Skip to main content

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.

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*}
Figure 1.4.2. Bit strings of arbitrary length and of length 4 and their respective unsigned and signed numbers. V indicates overflow.

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:

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

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.

202207281550
Hint.

Use the value table from Lemma 1.3.1

Answer.
\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. Bit strings of lengths 4, 3, and 2. Preserving the value under the unsigned interpretation means extending with zeros. Preserving the value under the signed interpretation means replicating the most significant bit.

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:

\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*}