==================================== Signed integers and integer overflow [TOC] ==================================== Note that May 1st is a holiday! Session 4 is scheduled for Tue May 5 (see __syllabus__). Video tutorial ============== ---- VIDEO ------------------------------ https://www.youtube.com/embed/k2WRHyOhfpE ----------------------------------------- Notations and conventions ========================= We now have introduced a new notation for indicating how a bit pattern get interpreted in a certain context. With ---- LATEX --------------------------------------------------------------------- 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. ---- LATEX --------------------------------------------------------------------- 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. ---- LATEX --------------------------------------------------------------------- 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: ---- LATEX --------------------------------------------------------------------- \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 ---- LATEX --------------------------------------------------------------------- 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 ---- LATEX --------------------------------------------------------------------- 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. ---- LATEX --------------------------------------------------------------------- \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 ---- LATEX --------------------------------------------------------------------- -s(B) < 0 \quad\Leftrightarrow\quad s(B) \geq 0 -------------------------------------------------------------------------------- After substitution, we infer from above that for subtraction we have ---- LATEX --------------------------------------------------------------------- \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__. ---- BOX ----------------------------------------------------------------------- Complete the sub-circuit `OF` such that it determines the overflow for signed addition and subtraction: - The sub-circuit has inputs `A`, `B`, `S` and `add/sub` and an output `OF`. - For `add/sub`=0 `OF` is supposed to indicate an overflow for signed addition of $s(A) + s(B)$, and for `add/sub`=0 `OF` is supposed to indicate an overflow for signed subtraction $s(A) - s(B)$. -------------------------------------------------------------------------------- :links: syllabus -> doc:syllabus HPC0: 4-bit statusregister assignment -> https://circuitverse.org/users/20564/projects/80249 :navigate: up -> doc:index back -> doc:session04/page01 next -> doc:session04/page03