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?

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, Sep 27 '15 at 06:26
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, Sep 27 '15 at 06:29
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, Sep 27 '15 at 06:38
@RaymondChen, ok, can you please show me how to do `2-1` using four bits? — Max Koretskyi, Sep 27 '15 at 06:50
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](http://sandbox.mc.edu/~bennet/cs110/tc/add.html) for examples. In your example the result is `0001` with carry `1` — M.M, Sep 27 '15 at 08:03
Can you describe the programming problem you're having? So far, this seems like a question about the theory of computation , not a practical programming problem. Are you trying to store a signed value in a 4-bit field and want to detect overflow? Please share code. — Raymond Chen, Sep 27 '15 at 14:50
@RaymondChen, I'm trying to understand how to subtract two numbers, for example `2 - 1` — Max Koretskyi, Sep 28 '15 at 11:00

score 39 · Answer 1 · answered Oct 06 '15 at 02:34

39

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.

answered Oct 06 '15 at 02:34

GabrielOshiro

7,986
4
45
57

thanks, I'm going to read a bit about `carry flag` and `overflow flag` and get back with questions) – Max Koretskyi Oct 06 '15 at 07:55
So what happens after an overflow is fount? Especially how to represent -9 in a 4-bit register? Is it like '1111' (or like '0111') in the register and indicating that there is an extra '0' (or a extra '1') bit in the answer using a flip-flop? – Midhunraj R Pillai Jan 07 '21 at 16:03
I will clarify the question. in case of -9, the actual answer is 10111. And in the case of +8, the answer should be 01000. So how does the computer know if the overflow bit is going to be 0 or 1? – Midhunraj R Pillai Jan 07 '21 at 16:16
Many processors define a 'sign' bit flag as 'negative xor 2s complement overflow'. You have shown that the overflow is really 'negative xor carry'. But doesn't that imply that the 'sign' bit is always the same as carry? Is there a counter-example in which a 2s complement addition leaves 'negative xor overflow' different than 'carry'? But if they are always the same why bother having a sign flag? – sprinter Apr 25 '22 at 10:42
@sprinter For 2's complement the sign bit is simply the leftmost bit, the beauty of 2's complement is that the sign bit is calculated just like any other bit. "You have shown that the overflow is really 'negative xor carry'" No! The sign bit of the result xor carry. "But doesn't that imply that the 'sign' bit is always the same as carry?" No, and that difference is what we use to identify the overflow. "Is there a counter-example..." Check the examples I gave, but this time use the result sign bit and the carry flag. More examples here https://en.wikipedia.org/wiki/Two%27s_complement – GabrielOshiro Apr 26 '22 at 16:00
1

@GabrielOshiro thanks for that explanation. I realise my comment was very ambiguous - sorry. I was actually thinking of the ATMEGA328 MCU when I posted that which has separate carry (C), sign (S), 2's complement overflow (V) and negative (N) flags in its status register. The N flag is the 2's complement sign (i.e. the MSB). The S flag is defined as 'always V xor N'. Your clear explanation of how to calculate V (as C xor N) left me wondering what the point of the S flag is on that processor. It's not explained at all well in the datasheet. – sprinter Apr 26 '22 at 20:29
@GabrielOshiro I posted a separate question on this https://stackoverflow.com/questions/72020883/on-an-avr-mcu-how-does-the-s-flag-in-the-status-register-work – sprinter Apr 26 '22 at 21:46
@sprinter Thank you! I'll definitely take a look – GabrielOshiro Apr 26 '22 at 22:38

score 4 · Answer 2 · answered Feb 25 '18 at 21:22

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

How is overflow detected in two's complement?

2 Answers2

Linked