Question

The algorithm ADDN implements N-bit fixed-width binary addition for non-negative integers and ignores overflows. For example, ADD4((1101)2,(1100)2) = (1001)2 because (1101)2 + (1100)2 = (11001)2 but the leading bit can’t fit in the 4-bit register. A standard way for computers to represent negative integers is the "two’s complement" method TN (x). Non-negative integers from 0 to 2N−1 − 1 are represented using ordinary fixed-width binary (e.g. T4(3) = (0011)2), and a negative integer n with −2 N−1 ≤ n is represented using the binary expansion of the (positive) integer 2N + n (e.g. T4(−3) = (1101)2 because 24 + (−3) = 13 = (1101)2). This representation allows us to use ADDN unchanged for both positive and negative integers! To partially prove this claim, show that if a and b are negative integers with −2 N−1 ≤ a + b, then ADDN (TN (a), TN (b)) = TN (a + b). (Hint: In what situation does ADDN (x, y) not equal x + y, and then what does it equal instead?)

Answer 1

This statement is true if and only if both left most bit of both numbers after conversion in 2's complement are different.

Explanation:

If both numbers left most bit is different in 2's complement then no overflow occur and the results of the equation are same.

ADDN (TN (a), TN (b)) = TN (a + b)

This equation satisfies if and only if, 2's complement of both binary number contains left most bit different. If the left most bit of both numbers is same then after addition the bits will be overflowed and result of addition in decimal and then convert to 2's complement will not be equal and above mentioned equation will not be satisfied.

It means that if both numbers have same sign, then 2's complement of both bit have same bits, if we add those numbers in decimal and add by converting them in 2's complement and add them both have different answers.