How is overflow detected in two's complement?

Question

I see that when I subtract positive and negative number using two's complement I get overflows. For example, if I subtract 1 from 2 I get:

2 = 0010
1 = 0001 -> -1 = 1111
2 + (-1) -> 0010 + 1111 = 10001

So here the result has fifth left bit 10001 - is it overflow? I've found these rules for detected overflows with two's complement:

If the sum of two positive numbers yields a negative result, the sum has overflowed. If the sum of two negative numbers yields a positive result, the sum has overflowed. Otherwise, the sum has not overflowed.

Can anyone please elaborate on these and show example?

Answer 1

Let's start with an answer to your title question.

How is overflow detected in two's complement?

Overflow rule : If two numbers with the same sign (both positive or both negative) are added, then overflow occurs if and only if the result has the opposite sign.

But you ask something different on the body of your question after your example.

So here the result has fifth left bit 10001 - is it overflow?

No! there is no overflow here. That fifth bit is the carry/borrow. Carry if you are talking about addition. Borrow if you are talking about subtraction.

Overflow occurs when the number that you trying to represent is out of the range of numbers that can be represented. In your example you are using 4-bits two's complement, that means you can represent any number in the range -8 (1000) up to +7 (0111). The result of your subtraction 2-1 is +1, a number that lies within the range of representation.

When we add a negative and a positive operand, the result will always be in the range of representation. Overflows occur when we add two numbers with the same sign (both positive or both negative) and the result has the opposite sign.

Most of misunderstanding surrounding carry-out and overflow comes from the fact we use the carry-out as one of the parameters to generate overflow flag. They are strongly related but they are not the same thing.

When adding numbers in two's complement, if the carry-out and the carry-on into the most significant bit (sign bit) are different that means an overflow has occurred.

Let's see two negative operands with a positive result:

-8 + (-1) = -9 

 1000  (carry)
  1000 (-8)
+ 1111 (-1)
------
  0111 (+7) OVERFLOW!

The carry-out is 1 and the carry-on to sign bit (MSB) is 0.

And now, an example of two positive operands with a negative result.

+7 + 1 = +8

 0111  (carry)
  0111 (+7)
+ 0001 (+1)
------
  1000 (-8) OVERFLOW!

The carry-out is 0 and the carry-on to sign bit (MSB) is 1.

Answer 2

@GabrielOshiro's answer is really good. I just want to add a little bit of logic here. When you add 2 and -1 together here,

2 = 0010
1 = 0001 -> -1 = 1111
2 + (-1) -> 0010 + 1111 = 10001

You should separate the most significant bit in the negative number from the rest of the bits, since in two's complement that bit brings negative value. So if you first add everything else first:

0010 + 0111(leave out the leftmost 1 for now) = 1001

After this, we can clearly see that the fifth bit in "10001" is caused by adding the "1" we left earlier (in fourth bit) with 1001, yielding a carry in the fifth bit. However, since this "1" should really cancel out with the 1001, leave us with 0001, we can safely ignore the extra bit in "10001" here.

A more in depth reasoning would be considering when we can safely ignore this extra bit and when we can't. As @GabrielOshiro mentioned, when the carry-out from and carry-on into the most significant are different we cannot ignore it. In a carry-out 2 units of negative numbers are lost because there's no space to hold the extra bit, and in a carry-in two units of positive numbers are lost, since what is supposed to be a unit of positive number is considered as a unit of negative instead. Here 1 - (-1) = 2. Therefore, a carry-on and a carry-out will cancel each other. But when only one of them occurs, the result will be incorrect thus we have an overflow.