# An Introduction to Imperative Programming

## Section1.4The 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.

### Definition1.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*}
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*}

### Remark1.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.
202306021614
Hint.
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*}

### Remark1.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:
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.
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.
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: