Skip to main content
\(\newcommand{\doubler}[1]{2#1} \newcommand{\binary}{\mathtt} \newcommand{\hex}{\mathtt} \newcommand{\octal}{\mathtt} \newcommand{\prog}{\mathtt} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section3.6Arithmetic Errors—Signed Integers

The number of bits used to represent a value is determined at the time a program is written. So when performing arithmetic operations you cannot simply add more digits (bits) if the result is too large, as you can do on paper. You saw in Section 3.1 that the C condition flag indicates when the sum of two unsigned integers exceeds the number of bits allocated for it.

In Section 3.4 you saw that carry is irrelevant when working with signed integers. In this section you will see that adding two signed numbers can also produce a result that exceeds the range of values that can be represented in the allocated number of bits.

The flags register, CPSR, provides a bit, the overflow condition flag, V, for detecting whether the sum of two \(n\)-bit, signed numbers stored in the two's complement code has exceeded the range allocated for it. Each operation that affects the overflow condition flag sets the bit equal to the exclusive or of the carry into the highest-order bit of the operands and the ultimate carry. For example, when adding the two 8-bit numbers, \(\hex{15}\) and \(\hex{6f}\text{,}\) we get:

carry \(\longrightarrow\) \(\binary{0}\) \(\binary{1} \longleftarrow\) penultimate carry
\(\binary{0001}\) \(\binary{0101}\) \(\longleftarrow\) \(x\)
\(+\) \(\binary{0110}\) \(\binary{1111}\) \(\longleftarrow\) \(y\)
\(\binary{1000}\) \(\binary{0100}\) \(\longleftarrow\) sum

In this example, there is a carry of zero and a penultimate carry of one.

In this example, there is a carry of zero and a penultimate carry of one. The V flag is equal to the exclusive or of carry and penultimate carry:

V = C ^ penultimate carry

where ‘^’ is the exclusive or operator. In the above example:

V = 0 ^ 1 = 1

There are three possible cases.

Case 1:.

The two numbers are of opposite sign.

Let \(x\) be the negative number and \(y\) the positive number. Then we can express \(x\) and \(y\) in binary as:

\begin{gather*} x = \binary{1} \dots\\ y = \binary{0} \dots \end{gather*}

That is, the high-order bit of one number is \(\binary{1}\) and the high-order bit of the other is \(\binary{0}\text{,}\) regardless of what the other bits are.

First, we can see that \(x + y\) always remains within the range of the two's complement representation:

\begin{align*} -2^{(n-1)} &\leq x \leq 0\\ 0 &\leq y \leq +(2^{(n-1)} - 1)\\ -2^{(n-1)} &\leq x + y \leq +(2^{(n-1)} - 1) \end{align*}

Now, if we add \(x\) and \(y\text{,}\) there are two possible results with respect to carry:

  • If the penultimate carry is zero:

    carry \(\longrightarrow\) \(\binary{0}\) \(\binary{0} \longleftarrow\) penultimate carry
    \(\binary{1} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{0} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{1} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 0 ^ 0 = 0.

  • If the penultimate carry is one:

    carry \(\longrightarrow\) \(\binary{1}\) \(\binary{1} \longleftarrow\) penultimate carry
    \(\binary{1} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{0} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{0} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 1 ^ 1 = 0.

We conclude that adding two integers of opposite sign always yields \(\binary{0}\) for the overflow condition flag, so the sum is always within the allocated range.

Case 2:.

Both numbers are positive.

Since both are positive, we can express x and y in binary as:

\begin{gather*} x = \binary{0} \dots\\ y = \binary{0} \dots \end{gather*}

That is, the high-order bit of both numbers is \(\binary{0}\text{,}\) regardless of what the other bits are.

Now, if we add \(x\) and \(y\text{,}\) there are two possible results with respect to carry:

  • If the penultimate carry is zero:

    carry \(\longrightarrow\) \(\binary{0}\) \(\binary{0} \longleftarrow\) penultimate carry
    \(\binary{0} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{0} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{0} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 0 ^ 0 = 0. The high-order bit of the sum is zero, so it is a positive number, and the sum is within range.

  • If the penultimate carry is one:

    carry \(\longrightarrow\) \(\binary{0}\) \(\binary{1} \longleftarrow\) penultimate carry
    \(\binary{0} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{0} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{1} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 0 ^ 1 = 1. The high-order bit of the sum is one, so it is a negative number. Adding two positive numbers cannot yield a negative sum, so the sum has exceeded the allocated range.

Case 3:.

Both numbers are negative.

Since both are negative, we can express x and y in binary as:

\begin{gather*} x = \binary{1} \dots\\ y = \binary{1} \dots \end{gather*}

That is, the high-order bit of both numbers is \(\binary{1}\text{,}\) regardless of what the other bits are.

Now, if we add \(x\) and \(y\text{,}\) there are two possible results with respect to carry:

  • If the penultimate carry is zero:

    carry \(\longrightarrow\) \(\binary{1}\) \(\binary{0} \longleftarrow\) penultimate carry
    \(\binary{1} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{1} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{0} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 1 ^ 0 = 1. The high-order bit of the sum is zero, so it is a positive number. Adding two negative numbers cannot yield a positive sum, so the sum has exceeded the allocated range.

  • If the penultimate carry is one:

    carry \(\longrightarrow\) \(\binary{1}\) \(\binary{1} \longleftarrow\) penultimate carry
    \(\binary{1} \ldots\) \(\longleftarrow\) \(x\)
    \(+\) \(\binary{1} \ldots\) \(\longleftarrow\) \(y\)
    \(\binary{1} \ldots\) \(\longleftarrow\) sum

    This addition would produce V = 1 ^ 1 = 0. The high-order bit of the sum is one, so it is a negative number, and the sum is within range.

These results and those from Section 3.3 allow us to state the following rules when adding or subtracting two \(n\)-bit numbers:

  • If your algorithm treats the result as unsigned, the carry condition flag (C) is zero if and only if the result is within the \(n\)-bit range; V is irrelevant.

  • If your algorithm treats the result as signed, the overflow condition flag (V) is zero if and only if the result is within the \(n\)-bit range; C is irrelevant.

The CPU does not consider integers as either signed or unsigned. Both C and V are set according to the rules of binary arithmetic by each arithmetic operation. The distinction between signed and unsigned is completely determined by the program. After each addition or subtraction operation the program should check the state of C for unsigned integers or V for signed integers and at least indicate when the sum is in error. Many high-level languages do not perform this check, which can lead to some obscure program bugs.

The codes used for both unsigned integers and signed integers are circular in nature. That is, for a given number of bits, each code “wraps around”. This can be seen pictorially in the “Decoder Ring” shown in Figure 3.6.2 for three-bit numbers.

<<SVG image is unavailable, or your browser cannot render it>>

Figure3.6.2“Decoder Ring” for three-bit signed and unsigned integers. Move clockwise when adding numbers, counter-clockwise when subtracting. Crossing over \(\binary{000}\) sets C to one, indicating an error for unsigned integers. Crossing over \(\binary{100}\) sets V to one, indicating an error for signed integers.