# GATE2006-39

8.7k views

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?

1. $c_{out}\left ( \overline{a_{n-1}\oplus b_{n-1}} \right )$
2. $a_{n-1}b_{n-1}\overline{c_{n-1}}+\overline{a_{n-1}}\overline{b_{n-1}}c_{n-1}$
3. $c_{out}\oplus c_{n-1}$
4. $a_{n-1}\oplus b_{n-1}\oplus c_{n-1}$

edited
2
can anyone please give me explanation for this question .
2
I guess here all options are incorrect.
5
is C1 C2... Cn-1 denote Sum ? I think it should represent carry
0
4

this question got repeated after 11 years except the part that he confused using the word UNSIGNED it doesnt matter here the same conditions apply as we are adding 2's complement numbers

5

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

4

Number representation in 2's complement representation:

• Positive numbers as they are
• Negative numbers in $2's$ complement form.

So, the overflow conditions are

1. When we add two positive numbers (sign bit $0$) and we get a sign bit $1$
2. When we add two negative numbers (sign bit $1$) and we get sign bit $0$
3. Overflow is relevant only for signed numbers and carry is used for unsigned numbers
4. When the carryout bit and the carryin to the most significant bit differs

PS: When we add one positive and one negative number we won't get a carry. Also points $1$ and $2$ are leading to point $4$.

Now the question is a bit tricky. It is actually asking the condition of overflow of signed numbers when we use an adder which is meant to work for unsigned numbers.

So, if we see the options, B is the correct one here as the first part takes care of case 2 (negative numbers) and the second part takes care of case 1 (positive numbers) - point 4.  We can see counterexamples for other options:

A - Let $n=4$ and we do $0111 + 0111 = 1110$. This overflows as in $2's$ complement representation we can store only up to $7$. But the overflow condition in A returns false as $c_{out} = 0$.

$C$ - This works for the above example. But fails for   $1001 + 0001 = 1010$ where there is no actual overflow $(-7+1 = -6)$, but the given condition gives an overflow as $c_{out} =0$ and $c_{n-1} = 1$.

D - This works for both the above examples, but fails for $1111 + 1111 = 1110$ $(-1 + -1 = -2)$ where there is no actual overflow but the given condition says so.

Thanks, @Dilpreet for the link and correction.

edited by
1
it is given that numbers are unsigned ,so in that case i think answer should be A,

but if numbers are signed then option C is Correct.

@Digvijay and @Arjun sir correct me if i am wrong
2

Here, Cn - 1  is the MSB of result .

I m getting all options incorrect.

2
Yes, I guess its a typo in question. Ci should be carry at respective positions.
1

Sir in point 3) When we add two unsigned numbers and there is an out carry (from MSB position).

Now, see option D)1111+1111=1110 , isnot there a out carry?

Both are here unsigned numbers, So, why taking value of 1111 as -1. means then it will be signed bit.rt?

1
Point 3 was wrong. Here, we consider only signed numbers. I corrected it now.
0
I am also getting same answer i.e. A as explained by @parthak please correct me if I m wrong...!!!!!!11
6
For all the confused people who are saying A is the answer:

Read question again.  "We consider the addition of two 2′s complement numbers"

Lets take 7+7    0111  + 0111    (Assume our adder size is 4bits)
It should be +14. Right ?
+14 is not   1110 in 4 bit 2's complement representation.   1110 means  -2.
So +14 cant be represented using 4bits in 2's complement representation.
So it is an overflow.

But apply option A, it says it is not an overflow.  (You are thinking it correct because you are thinking 0111+0111 = 1110 is fine with no overflow,  & that word unsigned is confusing you.  Question says...The numbers we have taken are 2 2's complement numbers.)
3

@Arjun sir @Digvijay

shouldn't the ans should be Bn-1.An-1.(Cn-1)c   + (Bn-1)c.(An-1)c.Cn-1

(Cn-1)c=Complement of Cn-1

0
@Bad_Doctor  yes there is a typo in option "B" in part B second term individual complement of a & b should be there
0
This works for the above example. But fails for   1001+0001=1010 where there is no actual overflow (-7+1 = -6), but the given condition gives an overflow as cout=0 and cn−1=1.

i am getting cout and cin as 0 how 1 come from cn-1
0

1001+0001=1010

1+0=1

So, cn−1=1. obviously true

5

The sum is denoted by $c_{n−1}c-{n−2}…c_{0}$

actually the sum is denoted by $s_{n-1 }s_{n-2}....s_{0}$

that  is why c) wrong

A'B'C+ABC'

Answer should be B. But I think there is a typo in B.

### My answer:- A N-1B N-1CN-1’ +  A N-1’B N-1’CN-1

0
How did you written the overflow  values in truth table
0

@akshat Sinha As given in Question that its unsigned integer so why you are considering an-1 and bn-1 as 1 in Truth Table.

Negative number cannot be consider as per Question?

0

"Now the question is a bit tricky. It is actually asking the condition of overflow of signed numbers when we use an adder which is meant to work for unsigned numbers."

So we need to calculate the condition of overflow of signed numbers which I mentioned above.

0

Using Kmap. we need to draw a a Kmap for it.

B'C'
B'C
BC
BC'
A'
0
1
0
0
A
0
0
0
1

suppose i m taking two +ve no and two -ve no and we perform its addition in two's complement no

 +70 0 1 0 0 0 1 1 0 +80 0 1 0 1 0 0 0 0 add 1 0 0 1 0 1 1 0 cout msb c(n-1)

here no carry is transfered to cout but c(n-1) is transfered to msb

 -70 1 0 1 1 1 0 1 0 -80 1 0 1 1 0 0 0 0 add 1 0 1 1 0 1 0 1 0 cout msb c(n-1)

here carry is transfered to cout and no c(n-1) is trasfered to msb

therefore,cout' c(n-1)+cout c(n-1)' =cout XOR C(n-1)

and another notable point is that there is no condition for overflow for +ve nd -ve no and also for -ve and +ve no

edited

Option (c) is correct

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

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

## Related questions

1
8.3k views
Consider numbers represented in 4-bit Gray code. Let $h_{3}h_{2}h_{1}h_{0}$ be the Gray code representation of a number $n$ and let $g_{3}g_{2}g_{1}g_{0}$ be the Gray code of $(n+1)(modulo 16)$ ... $g_{3}(h_{3}h_{2}h_{1}h_{0})=\sum (0,1,6,7,10,11,12,13)$
Given two three bit numbers $a_{2}a_{1}a_{0}$ and $b_{2}b_{1}b_{0}$ and $c$ ...
Consider the circuit above. Which one of the following options correctly represents $f\left(x,y,z\right)$ $x\bar{z}+xy+\bar{y}z$ $x\bar{z}+xy+\overline{yz}$ $xz+xy+\overline{yz}$ $xz+x\bar{y}+\bar{y}z$
You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of $f$ by $180°$?