# 2's complement subtraction with overflow

I studied binary subtraction using 2's complement method and understood the rules, which say that after the subtraction process (actually addition) discard any carry in case it occurs and take the answer as it is (with positive sign). In case there's no carry take the 2's complement of the answer and represent it in decimal form with a negative sign.

Now I came across the concept of overflow. It says, in case there's no carry in to the sign bit but there's carry out from it then it indicates an overflow. The correct solution of the subtraction is this number with overflow (or carry) bit included (but it is in complemented form).

In this second case of overflow we are not discarding the carry bit but considering the complete solution. But earlier we were discarding the carry. So how do I deduce new rules to be considered for subtraction using 2's complement in case overflow occurs?

EDIT:

In this example the correct answer was obtained by discarding the end carry

But here, where there is an overflow, the end carry is not discarded for getting the actual result (1 0110 1010 = -150 in binary 2's compliment form). Had we removed the end carry as in earlier example, the result would have been 0110 1010 = +106.

Both examples are employing different treatment on the occurrence of a Carry. Are my observations faulty?

• Do you have an issue regarding subtracting numbers? Maybe you should post a new question about a practical implementation of your problem. From my point of view, I never had troubles subtracting signed numbers, even if there is an overflow. You should start with 8 bit signed number and a piece of paper and pencil. So let me know where the real problem is. Feb 13, 2020 at 9:40
• I think you need to show some examples of what you do understand and what kind of situation you are asking about. Feb 13, 2020 at 14:49
• @Elliot Alderson I've added the example problems Feb 13, 2020 at 19:06
• @Marko I've added the example problems Feb 13, 2020 at 19:07

You didnt state your "rules" so we dont know how to understand "new rules", complete solution, etc. If you use a flag based architecture then both C and V are important/desired. If not a flag based architecture you still compute them but do the comparison in the same instruction.

As you perhaps understand, in binary math, that first off you dont subtract you add

x - y = x + (-y) = x + (~y + 1) = x + (~y) + 1

and you might have figured out that the same logic is used for signed and unsigned addition/subtraction that is the beauty of twos complement. the logic/hardware doesnt care (multiply and divide are a different story with respect to signed/unsigned)

 00000
0001
+ 1110
=======
1111


now is that 1 + 14 = 15 or is that 1 + -2 = -1? yes it is both at the same time the logic doesnt care, only the human cares if those are unsigned or signed numbers.

Now first off unsigned overflow

     0
1111
+ 0010
=======

11100
1111
+ 0010
=======
0001


the carry out from the msbit is the carry out for the adder and indicates unsigned overflow if set. there isnt room to store the value but notice that if we were to look at this as -1 + 2 = 1 then there is no signed overflow. Two equivalent ways to determine signed overflow are. If the msbit of the operands (as viewed in the adder) is the same and the msbit of the result is different from the operands then it is an overflow otherwise not. So if the msbits of the operands different it is not a signed overflow if all three msbits are the same it is not a signed overflow otherwise it is. I find it easier to examine the carry in and carry out of the msbit, if they differ then it is a signed overflow if they match as in this case it is not.

so with 4 bits -4 = -100 = 1011 + 1 = 1100 so -4 - 5 = -9, -9 cannot be represented in 4 bits so

    1
1100
+1010
========

10001
1100
+1010
========
0111


so we see that the msbits of the operands are 1, the msbit of the result is 0, signed overflow. we can also look at the carry in of the msbit (0) and the carry out of the msbit (1) and they dont match, signed overflow.

The carry/borrow bit is very useful to preserve no reason to discard. Already saw it above as a unsigned signed overflow. For subtraction it represents a borrow.

 1000000
-      5
==========


you cant subtract 5 from 0 in that first column, so you have to borrow, in this case that borrow cascades its way all the way across to the left end where it borrows that 1 and we have 999999 - 5.

In grade school math we cant subtract 5 from 3 instead we subtract 3 from 5 then negate the result. But in binary logic we can subtract 5 from 3.

    1
0011
+1010
======

00111
0011
+1010
======
1110


3 - 5 is -2 with a carry out of 0, what if we subtract 5 from 3 (different equation just using the same two numbers)

    1
0101
+1100
=======

11011
0101
+1100
=======
0010


5 - 3 = 2. the carry out is a 1. you can work through all combinations, but the carry out for a subtract means not borrow.

So for subtraction you invert the second operand and invert or make 1 the carry in (invert and add 1). Some architectures invert the carry out for a subtract to call it a borrow bit, some simply leave the carry out as is and understand it is a not-borrow bit.

As with addition you can cascade this borrow. Think invert the carry in during a subtract with borrow if you implement that, dont just think of the carry in on a subtract as always being a 1. If I were to cascade the borrow I need to steal a 1 from the higher level subtraction, so instead of a carry in on subtract being a 1 always, I need to borrow that one to give to the lower ordered bits, so you carry in a 0 to facilitate that borrow. A subtract without borrow (a normal subtract) the normal carry in is a 0 for addition, for subtraction you invert that to make it a 1. For a subtract with borrow you take the borrow flag from the lower ordered subtraction and you invert that to make it the carry in. If there was no borrow then inverted it is a 1 if there was a borrow we borrow that 1 and carry in a 0

20 - 5 = 00010100 - 00000101

subtract

00001
0100
+1010
======
1111


inverting the carry out we have borrow = 1

now a subtract with borrow we invert the borrow as our carry in.

11110
0001
+1111
======
0000


so 20 - 5 = 0xF = 15, and we performed that with a subtract and then a subtract with borrow in the same way that with addition we would use add and then add with carry.

So for subtract invert the carry in, invert the second operand, and it is your choice architecturally to invert or not invert the carry out when done. Some architectures you see/touch every day invert, and others do not. If you dont invert and then have a subtract with borrow or a subtract with carry then you dont invert the carry bit you take it in as is.

Note that in this case neither one of these overflowed. Some architectures that have say 8 bit registers that can be combined as 16 bit registers (and so on) for an 8 bit add/subtract have one V flag but for the 16 bit alu there are two v flags one for the 8 bit part and one for the 16 bit part , a sort of half overflow just in case someone cared. This is again an architecturally specific design choice, in that case you would compare either bit 7 of the operands to bit 7 of the result or compare the carry in and carry out of bit 7 for the half overflow flag and bit 15 for the overflow flag.

As far as the term overflow, there is often a v flag to indicate overflow, in your brain when you read these terms think of the carry flag as "unsigned overflow" and the v flag as "signed overflow" (for addition and subtraction), you might say overflow in conversation but think signed overflow, even better SAY signed overflow in conversation for clarity and unsigned overflow when it makes sense to use that term.

Again this is for addition and subtraction. How the flags are used for multiplication and division is another exercise.

EDIT

If you wanted to do -70 + -80 = -150 then first off that is addition not subtraction so no inversions happen, the overflow is there though:

        0
10111010
+10110000
==========

101100000
10111010
+10110000
==========
01101010


Two msbits are the same answer is different. carry in and carry out of the msbit differs so this is a signed overflow right answer is 0x16A but that cannot be represented in 8 bits so it is 0x6A with a signed overflow.

understand that the carry out DOES NOT just fall through to do -70 + -80 = -150 with 9 bit math you have to sign extend the operands one more bit.

1101100000
110111010
+110110000
===========
101101010


its not 1+0+0 = 1 carry the 0 in that msbit it is 1+1+1 = 1 carry the 1, if you were to not sign extend then the carry out and carry in would not match for the msbit and you would have an overflow which would be incorrect.

If you were to do subtraction then I think it makes a difference to not put the full negative number for the second operand, invert (ones complement) and use the carry in for the plus one. Hmm maybe that does work let me think about it.

EDIT

Okay fair enough for all the bit patterns it still works. And that makes sense now that I see it. When implementing this in logic though you dont do the 2s complement on the second operand because that is an additional add operation, the inversion is simple, and the adding one by using the carry in is simple so I guess I always see it that way. if your professor wants it the other way then fine.

For the first example you dont drop the msbit down, that is off the end of the adder that is the carry out. you always discard the end carry with respect to the result. if there is an overflow (signed or unsigned) then the result is wrong as expected, if there is no overflow then the answer is right. that is the whole point of the overflow to tell you the answer is wrong

The first example the msbit of the first operand is a 1 the msbit of the second operand is a 0 it is not possible to have a signed overflow, the carry out is never part of the answer for fixed bit binary math. maybe you can also see why I show all the carry bits when I implement the math and never drop the carry out to the result, this is not grade school decimal math where we have an infinite number of digits/storage slots for the result.

• I've added examples. Hope it clarifies the question! Feb 13, 2020 at 19:08