Overflow

Introduction

As you've been reading though various int representations (unsigned binary, SM, 1C, 2C), you know that these representations represent a finite number of values. Thus, they have a minimum value and a maximum value, which I'll refer as min and max.

While we're interested in representating numbers, we're just as interested in using the numbers to do arithmetic (e.g., adding, subtracting, multiplying, dividing).

It's assumed that operations are performed on valid values. All signed and unsigned representation systems map every bitstring pattern to some value integer value. There are no invalid bit patterns, i.e., bit patterns that map to some nonsense value.

However, even though operations are performed on valid values, the result of the operation may not be valid. There's always an answer produced, but that answer may not be correct.

Defining "overflow"

Overflow occurs when the resulting value of an operation performed on valid representations of numbers is out of the range of valid values. That is, the resulting value is greater than max or less than min.

Caveat

How overflow occurs depends:

the operation being performed,
the representation system used to represent the numbers,
and the number of bits used

You need to realize that the representation system is important. We'll see this in an example.

Overflow in Unsigned Binary (UB)

If you are representing numbers using 4 bits as unsigned binary, the minimum value is 0 (i.e., 0000₂, while the maximum value is 15 (1111₂). Any operation that results in a number larger than 15 or smaller than 0 has overflowed.

For example, if you summed 14 + 14 (in UB, that's 1110 + 1110), the resulting value is 28, but the value 28 has no representation using 4 bits (since the maximum representable value is 15). Thus, there is overflow.

You might wonder, well, why not use 5 bits? Hardware has fixed number of bits. If it's 4 bits, then that's all you have to work with.

Detection of Overflow in UB

Detecting overflow in unsigned binary is straightforward. If adding the two values causes a N+1 bit result (this means that when you summed the MSb's plus any carry into the column of the MSBs, the resulting value had a carry to the next column), you have overflow.

However, this method of detecting overflow only works in UB. It doesn't work in 2C, for example.

Detection of Overflow in 2C

Consider the same bit pattern we used before: 1110 + 1110. In 2C, 1110 is the representation of the value -2. So, if you add -2 + -2, you get -4. This falls within the range of representable values in 2C, thus, there should be no overflow.

The addition of 1110 + 1110 results in 11100, which is 5 bits. You might think this means overflow, but let's see what happens.

Anytime an operation on two 4-bit numbers results in more than 4 bits, the highest bits are removed. Thus, you truncate the 5 bit result by removing the MSb of the 5-bit number. Therefore, you get 1100. 1100 is -4 in 2C using 4 bits.

Notice that detecting overflow in 2C is not the same as in UB. In particular, this sum resulted in 5 bits, but as long as you dropped the highest bit (and this is commonly done in hardware, because there's no way to magically create additional bits), it produces a valid representation for a valid value.

Detecting overflow in 2C is more difficult than UB. If you want, you can think about how to detect it, but it's much easier to do so once we discuss the hardware to do addition.

In principle, detecting overflow also depends on how you computed the result. For UB and 2C, we assume there's some adder circuit which performs addition by adding columns of digits from right to left (just as you were taught to add decimal numbers in elementary school). If the circuit did something different (say, it used a lookup table), then overflow detection might be even more difficult to judge.

Overflow detection and overflow are two different things, and it's importnat to keep that in mind. You should be able to tell when overflow occurs by converting the numbers to base 10, performing the operation and determining if the result is a valid number in that representation, even if you don't know how to, say, design a circuit that detects overflow in a certain representation.

Summary

Overflow occurs when an operation produces a result that's larger than the max value or smaller than the min value within a representation system.

Overflow is NOT the result of adding two N bit numbers and getting an N+1 bit result. This is a method for detecting overflow for adding 2 N-bit UB representations.

Keep in mind that there's a distinction between what overflow is, and how to detect overflow.

Note that overflow usually refers to operations performed on representations of integers. Overflow can occur in operations performed on floating point numbers too, but rarely to other non-numeric data types.

Web Accessibility