Difference between end carry and overflow

Problem Detail: 

I am confused with end carry and overflow. When will an end carry be the overflow? How to identify whether the end carry is overflow or not? Are they both same?

Sometimes end carries obtained are simply discarded and sometimes the end carries are considered as overflows. What is the exact method to find an overflow?

In the case of unsigned numbers, if the addition causes end carry, then the end carry should not be discarded because it is the part of result number. In this case, is the end carry an overflow? In the case of signed numbers, if the addition causes end carry, then the end carry represents sign bit. In this case is the end carry an overflow?

Asked By : hanugm

Answered By : Jared

I'm assuming we are talking about Two's Complement integers (positive and negative of course). You need to first understand the boundaries:

The largest positive value is:

$$ 2^{n - 1} - 1 = 0111\ 1111\ 1111\ ... $$

The "largest" negative (most negative value) occurs at:

$$ -2^{n - 1} = 1000\ 0000\ 0000\ ... $$

Adding any positive value to $2^{n - 1} - 1$ will result in an overflow! Likewise adding any negative value to $-2^{n - 1}$ will also result in an overflow (or perhaps more precisely and underflow--but that has a different meaning when it comes to floating point values).

It should be clear that adding anything "above" $1000\ 0000\ 0000\ ...$ ($-2^{n - 1}$) to $0111\ 1111\ 1111\ ...$ ($2^{n - 1} - 1$) will result in a carry! Yet by the above we know that adding any of these values $\geq 1000\ 0000\ 0000\ ...$ will simply be subtracting a value that results in a valid (possibly negative if it's $-1$) result. On the contrary, if we attempt to add a positive value such that the first digit is $0$, then we get no carry and yet we get overflow.

When we try to add two negatives ($1...$ and $1...$) we are bound to have a carry but this always results in $1\ 0000\ 0000\ ...$ added to some two's complement value.

The algorithm for determining overflow is very simple: if you add two positive numbers then you should get a positive and if you add two negative numbers then you should get a negative (and if you add a positive and a negative, you will never get the "wrong" result).

I don't know if that helps or not because I'm not too sure what you mean by "end carry".

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/29703