1
\$\begingroup\$

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:

enter image description here

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

enter image description here

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?

\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Feb 13, 2020 at 9:40
  • 1
    \$\begingroup\$ I think you need to show some examples of what you do understand and what kind of situation you are asking about. \$\endgroup\$ Feb 13, 2020 at 14:49
  • \$\begingroup\$ @Elliot Alderson I've added the example problems \$\endgroup\$
    – Bhuvnesh
    Feb 13, 2020 at 19:06
  • \$\begingroup\$ @Marko I've added the example problems \$\endgroup\$
    – Bhuvnesh
    Feb 13, 2020 at 19:07

1 Answer 1

3
\$\begingroup\$

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.

In grade school decimal math

 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.

\$\endgroup\$
7
  • \$\begingroup\$ I've added examples. Hope it clarifies the question! \$\endgroup\$
    – Bhuvnesh
    Feb 13, 2020 at 19:08
  • \$\begingroup\$ @Bhuvnesh I have added your problem to my answer. \$\endgroup\$
    – old_timer
    Feb 13, 2020 at 19:34
  • \$\begingroup\$ Ok, that's the story for our computers - that an overflow is always going to give incorrect results. But If we were to do it on a paper, is it possible to just look at result, not knowing whether an overflow has occurred or not, and tell what the correct answer would really be ! (Not on computer, but on paper). I am asking this because till the time overflow concept was not known to me I just used to do the arithmetic and apply the rules as described earlier and got the result. I did never think about of if there was an overflow. But would I need to consider that now onwards? \$\endgroup\$
    – Bhuvnesh
    Feb 14, 2020 at 4:10
  • \$\begingroup\$ if you want to do it on pencil and paper you need to sign extend and understand that that can go on forever if you add two negative numbers so you have to know when to stop. I can add 3+5 on paper and get 8 or I can add 3+7 and get 10 needing another column (and two implied zeros in front of the 3 and 7) \$\endgroup\$
    – old_timer
    Feb 14, 2020 at 16:07
  • \$\begingroup\$ absolutely a fair number of combinations of values result in an unsigned or signed overflow. with multiply it gets really bad since programming languages tend to have same sized inputs and outputs 32 bit result = 32 bit operand * 32 bit operand, a large percentage of those combinations fail. that is why you often see the machine instruction 64 bit result = 32 bit operand * 32 bit operand, but you will also see a signed and unsigned version and have to understand all of that. \$\endgroup\$
    – old_timer
    Feb 14, 2020 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.