Q) Let an−1an−2...a0 and bn−1bn−2...b0 denote the 2’s complement representation of two integers A and B respectively. Addition of A and B yields a sum S=sn−1sn−2...s0.The outgoing carry generated at the most significant bit position, if any, is ignored. Show that an overflow (incorrect addition result) will occur only if the following Boolean condition holds:

where ⊕ denotes the Boolean XOR operation and ~ denotes the boolean NOT operation. You may use the Boolean identity: X+Y=X⊕Y⊕(XY) to prove your result.

My Attempt :- When an−1bn−1(~sn−1) + (~an−1)∗(~bn−1)∗sn−1 is 1 then overflow OCCURS otherwise no overflow. Means when 2 positive numbers are added and answer is negative and when 2 negative numbers are added and answer is positive then overflow occurs otherwise it does not occur.
(sn−1)(an−1sn−1) + (~sn−1)(~(an−1sn−1))= bn−1(sn−1(~an−1)+ an−1(~sn−1))
After solving further, I am getting finally :-
sn−1an−1 + (~sn−1) = bn−1sn−1(~an−1) + bn−1an−1(~sn−1)

I don't know how to solve further to get the desired result and I also don't know whther I am going in right direction or not. Please help.

  • \$\begingroup\$ It's not clear what you are trying to accomplish. The CPU has CCR flags that tell you what's going on, other than using the CPU I don't understand how would you do this algebra. \$\endgroup\$ – Marko Buršič Mar 27 '19 at 11:44
  • \$\begingroup\$ @Marko, I also don't know what I was doing because I was not getting any clue how to solve it. Can you please tell me how to show the given boolean condition for overflow ? \$\endgroup\$ – ankit Mar 27 '19 at 13:46

I'll describe this in words, hopefully it will be easy to understand.

Consider the msb as the sign. If the numbers are opposite sign, then no overflow is possible.

If the signs are the same, and the result has a different sign from either of the two numbers, then overflow has occurred. Otherwise it has not.

  • \$\begingroup\$ I know these things but I want to know how to prove the given condition for the overflow in the question ? Can you please help @Spehro ? \$\endgroup\$ – ankit Mar 27 '19 at 15:37
  • \$\begingroup\$ @ankit, well l don't remember boolean algebra operations well enough to do this quickly in the form your homework probably requires, but there are only 8 entries in the truth table and the equality holds only for the appropriate two as I described: Sn-1 = 0 and An-1=Bn-1=1 is the first, and Sn-1 =1 and An-1=Bn-1=0 is the second. For what it's worth, the left ex-or could be replaced with or, with no change. \$\endgroup\$ – Spehro Pefhany Mar 27 '19 at 16:07
  • \$\begingroup\$ Thank you so much sir :) I did not think about truth table. \$\endgroup\$ – ankit Mar 27 '19 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.