GATE CSE 2006 | Question: 39

Question

We consider the addition of two $2's$ complement numbers $ b_{n-1}b_{n-2}\dots b_{0}$ and $a_{n-1}a_{n-2}\dots a_{0}$. A binary adder for adding unsigned binary numbers is used to add  the two numbers. The sum is denoted by $ c_{n-1}c_{n-2}\dots c_{0}$ and the carry-out by $ c_{out}$. Which one of the following options correctly identifies the overflow condition?

• A. $ c_{out}\left ( \overline{a_{n-1}\oplus b_{n-1}} \right )$
• B. $ a_{n-1}b_{n-1}\overline{c_{n-1}}+\overline{a_{n-1}}\overline{b_{n-1}}c_{n-1}$
• C. $ c_{out}\oplus c_{n-1}$
• D. $ a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$

Comments

$a_{n-1}, b_{n-1}$ represent the sign bits of first number and second number, $c_{n-1}$ represents the sign bit of the Sum of both numbers,
Case 1:
If two positive numbers(with sign bit 0) are added and the sign bit of sum is 1(-ve), then there is an overflow.

Case 2:
If two negative numbers(with sign bit 1) are added and the sign bit of sum is 0(+ve), then there is an overflow.

$Overflow : Case 1 + case 2 = a_{n-1}*b_{n-1}*c_{n-1}' + a_{n-1}'*b_{n-1}'*c_{n-1} $

Hence, option (B) is correct.

 

 

---

The best resource out there for understanding carry and overflow flags

---

Overflow condition can be written in any of the three ways – 

1. $C_{n} \oplus C_{n-1}=1$ which says that either 1st MSB or 2nd MSB should give carry but not both.
2. $A_{n}B_{n}\bar{C_{n-1}} + \bar{A_{n}}\bar{B_{n}}C_{n-1}=1$ where $A_n$ and $B_n$ are the MSB (which are sign bits) and $C_{n-1}$ is the carry from the 2nd MSB.
3. $A_{n}B_{n}\bar{R_{n}} + \bar{A_{n}}\bar{B_{n}}R_{n}=1$ where $R_{n}$ is the MSB (sign bit) of result of the addition.

From the third condition above, we can see that overflow will happen when:

 1. $A_n,B_n$ is 0 (which means positive numbers) and $R_n$ is 1 (which means a negative number).

2. $A_n,B_n$ is 1 (which means both are negative numbers) and $R_n$ 0 (which means a positive number).

Conclusion: For overflow to happen, two positive numbers are added and the result is negative OR two negative numbers are added and the result is positive.

PS: 2nd result can be derived from 1st result by replacing the value of $C_n$ with $A_nB_n + C_{n-1}(A_n \oplus B_n)$ and 3rd result can be derived from the 2nd result by thinking a bit. Let me know if you find it difficult to derive it.

Answer 1

overflow in case of unsigned number

*overflow is case of unsigned number occurred if carry is produced. e.g(101+110=1011)

overflow in case of signed number

*overflow is occurred only if  M.S.B of two number is same and there result is different.

in case of two positive number M.S.B be one and M.S.B of there result is 0 if overflow occurred

which is written as  an-1 .bn-1.c'n-1

in case of two negative number M.S.B be 0 and M.S.B of there result is 1 if overflow occurred

which is written as a'n-1.b'n-1.cn-1 

in combined case of postive and negative number overflow occurred

Overflow Expression: a'n-1.b'n-1.cn-1 + an-1 .bn-1.c'n-1

 

Answer 2

It took me long to analyse but After reading Carl Hamacher, I understood that overflow is occured when we talk of signed numbers only. For unsigned numbers we have carry bit to take care of the stuff.

Example

     1011 (-5)

 +  1000 (-8)

1   0011

This example is for signed, but if you see if we neglect carry out Cout then also we see the sign of An-1 and Bn-1 and Cn-1

So clearly for the clarity whenever be it signed or unsigned, if sign of An-1 == sign of Bn-1 then overflow occurs if sign of Cn-1 is complement of An-1

 

C is correct