How is overflow detected in two's complement?

9
votes

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?

2
binarybit-manipulationtwos-complement
Your last example is inconsistent. The value of -1 is given in four bits, but your answer is calculated in five bits. If you word size is 5 bits, then the value of -1 should be 11111, not 1111. In a 5-bit word, 1111 is the value 15, not -1. You calculated 2 + 15 = -15. Also, what is your programming question? (This isn't really a programming question yet.) – Raymond Chen
Sorry, I don't understand. I converted -1 to four bits, and then added and received five bits. How should I have done it differently? – Max Koretskyi
You added two signed 4-bit values and produced a 5-bit result, which invalidates the original calculation of the 4-bit values. It's like showing somebody a 1 liter bucket and telling them, "Fill it to all but 5ml." They put 995ml in it. You have another bucket with 10ml of water in it. You pour them both into a 10 liter bucket and say "Hey, the 10 liter bucket didn't overflow. That person put the wrong amount of water in the 1 liter bucket, because I expected it to overflow by 5ml!" – Raymond Chen
@RaymondChen, ok, can you please show me how to do 2-1 using four bits? – Max Koretskyi
You have to inspect the sign-bit, and the combination of sign bit and whether there was carry tells you whether there was overflow. See here for examples. In your example the result is 0001 with carry 1 – M.M

2 Answers

29
votes

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.

3
votes

@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.