Binary arithmetic - overflow and carryout at same time?
In binary arithmetic, When you subtract 2 signed numbers you must discard the carry out. My question is, is it possible for overflow to occur and a carry out? So, on paper there would be two extra bits and you would have to discard one?
Also, if your subtracting 2 signed numbers, how do you differentiate between overflow and a carry out?
$\endgroup$5 Answers
$\begingroup$Overflow and carry out are philosophically the same thing. Both indicate that the answer does not fit in the space available. The difference is that carry out applies when you have somewhere else to put it, while overflow is when you do not. As an example, imagine a four bit computer using unsigned binary for addition. If you try to add $1010_2+111_2$ without the word length restriction, you get $10001_2$ The high bit does not fit in our word. If this word is all the space allocated to this variable, it represents overflow as the result is too large to represent. If we have a two word space allocated to this variable, it becomes a carry out and is stored in the higher word. We would then represent the addition as $0000\ 1010_2+0000\ 0111_2=0001\ 0001_2$ and the carry is explicit.
$\endgroup$ 3 $\begingroup$You have 2 bits, C and V, so you have 4 options. I am going to use 8 bits for the number and other bit for the sign. With this sketch, we can represent numbers from -256 (1 0000 0000) to +255 (0 1111 1111). The first bit it is the sign: 0 it means positive and 1 means negative. Here are the options:
Normal add (it doesn't go further the upper boundary 255) like (+120) + (+100).$$\begin{array}{rrr} (0 &0111 &1000)\\ + (0 &0110 &0100) \\ \hline (0 &1101 &1100) \end{array}$$The bit sign didn't change, so the overflow becomes 0, and there is no carry present, so carry is 0.
Normal subtract (it doesn't go further the lower boundary -255) like (-250) + (-5).
To represent the -250 we have to do the complement plus 1.$$250 = 0\; 1111\; 1010 \\ \overline{250}= 1\; 0000\; 0101 \\ \overline{250}+1= 1\; 0000\; 0110$$To represent the -5 we have to do the complement plus 1.$$5 = 0\; 0000\; 0101 \\ \overline{5}= 1\; 1111\; 1010 \\ \overline{5}+1= 1\; 1111\; 1011$$And now we add$$\begin{array}{rrr}(&1& 0000& 0110)\\ + (&1 &1111& 1011)\\ \hline (1 &1 &0000 &0001) \end{array}$$Where the first one is the carry, and the sign bit didn't change, so the overflow bit is 0. The result number is a negative number. To find the number we have to go backwards.$$ \overline{1\ 0000\ 0001} = 0\ 1111\ 1110 \\ \overline{1\ 0000\ 0001}+1 = 0\ 1111\ 1111 $$So the result number is a negative 255.
Addition over 255 (it goes above the upper boundary 255) like (+250) + (+6). So$$\begin{array}{rrr}(0 &1111 &1010)\\ + (0 &0000 &0101)\\ \hline (1 &0000 &0000)\end{array}$$The addition of two numbers with the same sign results in a number with different sign what is wrong, so the overflow bit V is set to one, and there is no carry in this operation, so the flag C is 0. This operation it must return a error because the number it can't be represented.
Subtract over -256 (it goes below the boundary -256) like (-250) + (-7).
To represent the -250 we have to do the complement plus 1.$$250 = 0\; 1111\; 1010\\ \overline{250}= 1\; 0000\; 0101\\ \overline{250}+1= 1\; 0000\; 0110 $$To represent the -7 we have to do the complement plus 1.$$7 = 0\; 0000\; 0111 \\ \overline{7}= 1\; 1111 \;1000 \\ \overline{7}+1= 1\; 1111\; 1001$$And now we add$$\begin{array}{rrrr}(&1& 0000& 0110)\\ + (&1 &1111 &1001) \\ \hline (1& 0& 1111& 1111) \end{array}$$Where the first one is the carry C, so the carry flag is set to 1, and the sign bit has changed, so the overflow bit is 1. This operation it must return a error because the number it can't be represented.
When you subtract two signed numbers, the Carry flag is irrelevant; the Overflow flag is all that counts. The Carry flag is for unsigned integer operations. So there is only ever one bit to worry about.
$\endgroup$ $\begingroup$Yes, you can have an overflow and a carry flag in the same operation. This is because an overflow flag is hooked up to an XOR gate, where the inputs are the carries from the two bits on the left. The carry flag gets triggered if there is a carry on the left most bit (the signed bit for signed numbers). So if you have a carry on the left most bit, but not on the one second from the left, you have an overflow and a carry. If you have a carry on the bit second from the left and not on the left most bit, you have only an overflow.
Here's a picture of an adder/subtractor where the V is the overflow, and the C is the carry. Each bit of the sum is calculated using a full adder, and each bit may have a carry. V is an XOR gate connected to the two left most carries.
What the overflow represents is when an operation causes the sum to fall outside the maximum or minimum bounds. For example, with an 8 bit signed operation, the maximum number of the sum is 255. while the minimum is -256.
So if you try to do 255 + 1 (01111111 + 00000001) you get an overflow. Notice how there was a carry on the second bit from the left, but not the left most. The sum comes out as -256, which is wrong.
An example where you get both an overflow and a carry would be -64 + (-256) (11000000 + 10000000). There is a carry on only the left most bit. The sum comes out as 64, which is wrong.
An example where you get only a carry would be -64 + 64 (11000000 + 01000000). There is a carry on both the left most and second from the left. The sum comes out as zero, which is right.
$\endgroup$ $\begingroup$In processors, overflow flag indicates that sign bit has been changed during adding or subtracting operations But carry flag means adding or subtracting two registers has carry or borrow bit.
$\endgroup$ 1
