Overview     Home     Back     Up     Next     1    2    3    4 Content of this session

Signed integers and status register for the ALU Signed integers and integer overflow Video tutorial Notations and conventions Representable integer ranges Integer overflow Computing CF Computing OF Assignment Extending bit patterns More about the status register and its relevance for programming

    Browse Files

Signed integers and integer overflow

Note that May 1st is a holiday! Session 4 is scheduled for Tue May 5 (see syllabus).

Video tutorial

Notations and conventions

We now have introduced a new notation for indicating how a bit pattern get interpreted in a certain context. With

\[s(b_{n-1} b_{n-2} \cdots b_0) := u(b_{n-1} \cdots b_0) - 2^{n-1} b_{n-1}\in \left\{ -2^{n-1}, \dots, 2^{n-1}-1 \right\}\]

we express that an \(n\)-bit pattern is interpreted as signed integer. If \(b_{n-1} = 1\) then this signed value is negative, otherwise it is non-negative (or not negative), i.e.

\[s(b_{n-1} \cdots b_0) < 0 \quad\Leftrightarrow\quad b_{n-1} = 1. \]

Note that non-negative means that a value can be zero or positive. That means: “the opposite of negative is not positive, it is zero or positive”!

In a \(n\)-bit pattern \(b_{n-1} \dots b_0\) the bit \(b_{n-1}\) is called the most significant bit (MSB) and \(b_0\) the least significant bit (LSB). In general one can say that the significance of a bit \(b_k\) depends on its index \(k\). So \(b_1\) is more significant than \(b_0\), \(b_2\) is more significant than \(b_1\) etc. You can motivate this convention by considering the interpretation as unsigned integer, i.e.

\[u(b_{n-1} b_{n-2} \cdots b_0) := (b_{n-1}, b_{n-2}, \cdots b_0)_2:= \sum\limits_{k=0}^{n-1} b_k 2^k\]

If you change the value of one bit \(b_k\) you change the correlated unsigned value. The higher you select \(k\) the more significant is the corresponding effective change.

Representable integer ranges

With \(n\) bits you can represent unsigned integers in the range from \( 0 \) to \(2^{n}-1\) and signed integers in the range from \(-2^{n-1}\) to \(2^{n-1}-1\). Most of the time we will work with 8-bit, 16-bit, 32-bit or 64-bit pattern. In order to have a guts feeling about what integer ranges can be represented here a list:

\[\begin{array}{lll}\text{bit pattern size} &\text{unsigned integer range} &\text{signed integer range}\\8 &0,\dots,255 &-128,\dots,127\\16 &0,\dots,65536 &-32768, \dots, 32767 \\32 &0, \dots, 4294967296 &-2147483648, \dots, 2147483647 \\64 &0,\dots, 18446744073709551616&-9223372036854775808, \dots, 9223372036854775807 \\\end{array}\]

Integer overflow

Overflow means that the result of an operation can not be represented with a given bit pattern size. Here we only consider the operations addition and subtraction. The carry flag (CF) indicates an overflow when interpreting bit patterns as unsigned integers, the overflow flag (OF) indicates overflow when interpreting bit patterns as signed integers. So in simple words:

• If you are looking at the bit patterns and think of them as an unsigned integer representation then you only care about CF. The value of OF does not make any sense for you.

• If you are looking at the bit patterns and think of them as a signed integer representation then you only care about OF. The value of CF does not make any sense for you.

Let \(A\) and \(B\) denote some \(n\)-bit pattern that are used for the representation of two operands and \(S\) an \(b\)-bit pattern used to represent the result of an operation. For addition

• the carry flag (CF) indicates with \(\text{CF}=0\) that we computed \(u(S) = u(A) + u(B)\) and

• the overflow flag (OF) indicates with \(\text{OF}=0\) that we computed \(s(S) = s(A) + s(B)\).

Analogously, for subtraction

• the carry flag (CF) indicates with \(\text{CF}=0\) that we computed \(u(S) = u(A) - u(B)\) and

• the overflow flag (OF) indicates with \(\text{OF}=0\) that we computed \(s(S) = s(A) - s(B)\).

These are formal descriptions of CF and OF, and for working with the ALU it is all we care about. However, we first have to build an ALU before we can work with it! So in this session we need to know how to determine the flags technically.

Computing CF

We know that for addition the adder computes \(c_\text{out}\) and \(S\) such that \(u(c_\text{out}S) = u(A) + u(B)\) and therefore \(u(S) = (u(A) + u(B)) \bmod 2^n\). Hence, for addition we have

\[u(S) = u(A) + u(B) \quad\Leftrightarrow\quad c_\text{out} = 0\]

and therefore we just use \(\text{CF} = c_\text{out}\).

We implemented the subtraction \(u(A) - u(B)\) by building the two's complement of the subtrahend \(u(B)\). Technically this was done by inverting the bits \(B\) and using \(c_\text{in}=1\) for the adder. Hence the adder computed \(u(S) = (u(A) - u(B)) \bmod 2^n\) and we had

\[u(S) = u(A) - u(B) \quad\Leftrightarrow\quad c_\text{out} = 1\]

So in case of subtraction CF is the inverted \(c_\text{out}\) bit, i.e. we use \(\text{CF} = 1 - c_\text{out}\).

Computing OF

Overflow for addition happens if the results \(s(A) + s(B)\) can not be represented with \(n\) bits. Analogously, an overflow for subtraction happens if \(s(A) - s(B)\) can not be represented with \(n\) bits.

For addition an overflow can not occur if \(s(A)\) and \(s(B)\) have different signs. For example, if \(s(A)<0\) and \(s(B) \geq 0\) then every value from \(s(A)\) to \(s(B)\) can be represented. Because of \(s(A) \leq s(A) + s(B) < s(B)\) the sum can be represented. In general an overflow for addition occurred if \(s(A)\) and \(s(B)\) have the same sign and the computed \(s(S)\) has a different sign, i.e.

\[\text{OF} = \begin{cases} 1, & (s(A) < 0) \land (s(B) < 0) \land (s(S) \geq 0) \lor (s(A) \geq 0) \land (s(B) \geq 0) \land (s(S) < 0), \\ 0, & \text{else}. \end{cases}\]

For subtraction we consider \(s(A) - s(B) = s(A) + (-s(B))\) and use

\[-s(B) < 0 \quad\Leftrightarrow\quad s(B) \geq 0\]

After substitution, we infer from above that for subtraction we have

\[\text{OF} = \begin{cases} 1, & (s(A) < 0) \land (s(B) \geq 0) \land (s(S) \geq 0) \lor (s(A) \geq 0) \land (s(B) < 0) \land (s(S) < 0), \\ 0, & \text{else}. \end{cases}\]

Assignment

For the assignment you can fork my project HPC0: 4-bit statusregister assignment.