Overflow in Arithmetic Addition in Binary number System
To explain the overflow of arithmetic addition, we are going to mostly use 2’s complement system, which is a type of widely used number system in computer architecture.
- If the 2’s complement number system has N- bit, it is able to represent a number from -2n-1 to 2n-1-1.
- If the 2’s complement system has 4 bit, it will represent the number from (-8 to 7).
- If the 2’s complement system has 5 bit, it will represent the number from (-16 to 15).
When we are trying to add 2 N-bit 2’s complement numbers, and the generated output is so large that it is not fitted into that N-bit group, in this case, overflow will occur with respect to addition. There are usually N bit fixed registers into a system or computer. When we add the two N- bit numbers, it will generate the output in max N+1 bit number. With the help of a carry flag, this extra bit is stored. The problem is that the carry does not always use to show an overflow.
For example: In this example, we are going to add 7 and 1 with the help of 2’s complement.
Solution: The addition of binary number 7(0001) and 7(0111) is described as follows:
As we can see that adding 7 + 1 with the help of 4 bit is equal to 8. But we cannot represent 8 with the help of 4 bit 2’s complement number because the number 8 is out of range. When we add two positive numbers, we just get a negative number (-8). In this example, 0 is also the carry. Normally the problem related to an overflow is left to the programmer, and he has to deal with these situations.
Overflow Detection
At the time of showing the result of arithmetic operation, if the bits are insufficient to represent the binary number, the overflow will occur. The computer arithmetic is closed with respect to division, subtraction, multiplication, and subtraction; due to this, an overflow occurs. If the signs of the operands are different(resp. identical), in this case, the overflow will not occur.
There are two cases when the overflow occurs, which are described as follows:
- When we try to add the two negative numbers and the generated result is a positive number.
- When we try to add the two positive numbers and the generated result is a negative number.
For example:
| INPUTS | OUTPUTS | ||||
|---|---|---|---|---|---|
| Asign | BSign | CARRY IN | CARRY OUT | SUMSign | OVERFLOW |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 |
When the two positive numbers are added, and the generated result is a positive number, and when the two negative numbers are added, and the generated result is a negative number, then there will be no overflow, which is described as follows:
| INPUTS | OUTPUTS | ||||
|---|---|---|---|---|---|
| Asign | BSign | CARRY IN | CARRY OUT | SUMSign | OVERFLOW |
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | ? |
| 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 | ? |
| 1 | 1 | 1 | 1 | 1 | 0 |
If we have n bit number representation, then we will need n + 1 bit to detect and compensate for an overflow. For example: Suppose we have 32-bit arithmetic, we can detect and compensate for overflow with the help of 33 bits. We can take a carry (borrow) which is occurred into the sign bit, to implement this in addition. To explain it more deeply, we are going to provide four different combinations of a sign with the help of four-bit long binary representations of numbers 7 and 6.
In place of using the 3-bit comparator, we can use the 2-bit comparator to detect the overflow. We can also detect the overflow with the help of checking the MSB of two numbers and their result. For this, we need to just check the Carry-in (C-in) and Carry-out (C-out) bits from Most Significant Bits. Suppose we are going to perform N bit addition of 2’s complement number, which is described as follows:
Overflow will occur when the C-in and C-out are equals to each other. With the help of below analysis, we can explain the above expression for an overflow.
In the first image, 0 shows the MSB of two numbers that indicate that they are positive. If we get 1 as Carry-in, the result of MSB will also be 1, which means that result is negative (Overflow). In this case, Carry-out will also be 0. It is proved that the Carry-in and Carry-out are not equal to each other, hence overflow.
In the second image, 1 shows the MSB of two numbers that indicate that they are negative. If we get 0 as Carry-in, the result of MSB will also be 0, which means that result is positive (Overflow). In this case, Carry-out will also be 1. It is proved that the Carry-in is not equal to Carry-out hence overflow.
With the help of above explanation, we can say that the overflow can be detected by the C-in and C-out at MSB (Most Significant Bit), which is described as follows:
With the help of above XOR gate, we can easily detect the overflow.
Conditions of Overflow
There are various conditions of an overflow, which are described as follows:
- The arithmetic operation has the capability that it can run into the overflow condition.
- On the basis of the size of data type, which will accommodate the result, the overflow is dependent.
- If the result’s data type is too small or too large that it is not fitted into the original data type, in this case, an overflow will occur.
- When we try to add the two signed 2’s complement numbers, the condition of an overflow will occur if both the numbers are positive and the generated output is negative, or if both the numbers are negative and the generated output is positive.
- When we try to add the two unsigned numbers, the condition of an overflow will occur if the left-most bit contains the carry-out.
Example of adding Unsigned numbers:
In this example, we use the one-bit quantities and detect whether the one-bit quantity contains an overflow or not.
In this example, we can see that the last line contains a carry output. That means we cannot accommodate (1 + 1) with the help of a one-bit quantity. If we want to succeed in the {1 + 1}, we need the large data type. When we try to add multi-bit unsigned numbers, the overflow will occur if and only if the left-most significant bit contains the carry-out.
Example of adding Signed numbers
In this example, we use the one-bit signed quantities and detect whether the one-bit quantity contains an overflow or not.
Solution: Here, one bit is used to indicate the sign, and another bit is used to indicate the data. Therefore, we need two-bit signed data types, which are described as follows:
| Binary | Decimal | |
|---|---|---|
| Sign Bit | Data Bit | |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | -1 |
| 1 | 0 | -2 |
Suppose we have two numbers with opposite signs. If we add those numbers, their sum will never overflow like this:
But if we have two same sign numbers, their sum can be overflow like this:
So the outputs {2, -4, -3} are not able to fit into the two-bit signed data type.