GATE IT 2004 | Question: 42

Question

Using a $4-bit$ $2's$ complement arithmetic, which of the following additions will result in an overflow?

1. $1100 + 1100$
2. $0011 + 0111$
3. $1111 + 0111$

• A. i only
• B. ii only
• C. iii only
• D. i and iii only

Comments

with 4 bits the range of 2's complement numbers is $-2^{n-1} to + 2^{n-1}-1)$ i.e. -8 to +7
1. sum = -8
2. sum = +10 (overflow)
3. Addition of two numbers of different sign never overflows.

hence, (b) is correct option!

---

Addition of a positive and a negative number can never lead to an overflow. Hence, (iii) is ruled out straightaway.

Overflow happens iff $MSB_p+MSB_q=\overline{MSB_r}$ ie, if the MSB of the result is different than the MSB of inputs.

$1100+1100=11000$ MSB of the result isn't different.

$0011+0111=1010$ MSB of the output is different. So, overflow.

 

Option B

---

Bro I have learnt a lot of things from your answers.

Answer 1

Only (ii) is the answer. 

In $2's$ complement arithmetic, overflow happens only when 

1. Sign bit of two input numbers is $0$, and the result has sign bit $1$
2. Sign bit of two input numbers is $1$, and the result has sign bit $0$.

Overflow is important only for signed arithmetic while carry is important only for unsigned arithmetic.

A carry happens when there is a carry to (or borrow from) the most significant bit. Here, (i) and (iii) cause a carry but only (ii) causes overflow. 

http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt

Comments

option (ii) is also causing overflow because both i/p sign bit are 0 , result has sign bit 1 whereas in (i) both i/p and o/p sign is same. No overflow occurs . So correct option is B.

---

Yes. (ii) causes overflow and not (i). Thanks for the correction :)

---

i understood the solution ....but why have they used the word  "2's complement arithmatic"

---

The statements in answer are applicable only for 2's complement arithmetic.

---

@Arjun Sir to detect overflow, we have boolean equation as

Overflow=$\left ( x_{k-1}+y_{k-1}+s_{k-1}^{'} \right )+\left ( x_{k-1}^{'}+y_{k-1}^{'}+s_{k-1} \right )$

where $k$=no . of bits

only option (i) matches

also if we convert it into decimal,

(i)$\left ( 1100 \right )_{2}=\left ( -4 \right )_{10}$

=$\left ( -4 \right )_{10}+\left ( -4 \right )_{10}=-\left ( -8 \right )_{10}$

=$\left ( 11000 \right )_{2}$ i.e overflow

same for (ii) sum is $\left ( 10 \right )_{10}=\left ( 01010 \right )_{2}$ overflow

https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/overflow.html

somehow similar to this

https://gateoverflow.in/118289/gate2017-1-9

---

@sourav

Overflow simply happens $C_{out}\oplus C_{n}=1$

---

yes you are right !@srestha .but it is one of the boolean equation which you have given.Another one is

https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Comb/overflow.html.

Also if i follow $C_{in}$XOR $C_{out}$, answer is not coming right! 

---

but is all two remember important? One formula can derive another. Isnot it?

---

both should be important!

---

@sourav with ur formula can u tell me

is 1111+1111 a overflow or not?

by that formula it is getting an overflow, but actually there is no overflow rt?

---

$1111+1111$, will not generate overflow!

$1111 \Rightarrow -1$

$1111+1111=-1(+)-1=-2=1110$,

 

Also if i apply the boolean function, overflow is not coming,!

---

overflow is for signed representation

So, 0111 is 7

then 1111 isnot it -7?

---

i have tried verifying without using boolean equation

overflow=$(a_{n-1}.b_{n-1}.s_{n-1}^{'})+(a_{n-1}^{'}.b_{n-1}^{'}.s_{n-1})$.

As in the question it is clearly written that

Using a 4-bit 2's complement arithmetic

so MSB must be a sign bit, using this approach , i converted $1111$ to $(-1)_{10}$

and proved that overflow is not occuring as-:$1111+1111$=$(-2)_{10}$=$1110_{2}$.

Also if you apply the boolean equation ,

$a_{n-1}=1$,$b_{n-1}=1$,$s_{n-1}=1$

so overflow=$1.1.0+0.0.1=0$,hence  no overflow for $1111+1111$

---

Rather than mugging any kind of formula even it is possible to answer this question provided we know to find range in 2's complement. Here range is from -8 to 7.

option a gives : -8

          b gives :10

          c gives : 6

---

so  the correct option is (b)

---

Also note: Adding 2 different signed data → Overflow can never occur

Answer 2

$($ Carry of $n-1^{th}$ $\oplus$ Carry of $n^{th}) = 1$ Then overflow in 2's complement

$\text{Format of a number here}:\color{green} {C_4}\color{red}{C_3}C_2C_1C_0$ 

In above format $C_4$ is $n^{th}$ carry

$(i) \space 1100 +1100 = 1000 $  Here $C_{n-1} = 1 , C_n = 1$  so $C_{n-1}\oplus C_n = 1 \oplus 1 = 0$

$(ii) \space 0011 +0111 = 1010 $  Here $C_{n-1} = 1 , C_n = 0$  so $C_{n-1}\oplus C_n = 1 \oplus 0 = 1$

$(iii) \space 1111 +0111 = 0110 $  Here $C_{n-1} = 1 , C_n = 1$  so $C_{n-1}\oplus C_n = 1 \oplus 1 = 0$

So option $B$ is only right choice

Answer 3

we can also use overflow logic----->
OV(x,y,z) =x'y'z + xyz'
where x is msb bit of operand 1.y is msb bit of operand 2.And z is msb bit of result excluding carry.

Comments

@saurabh

so what when the result is 1 what it means

and when 0 what is signify ? illustrate that

Answer 4

D) (i) and  (iii) only.

Please comment if anyone finds it wrong !

Comments

(iii) will not result in an overflow. Please see the selected answer.