Consider Z = X – Y, where X, Y and Z are all in sign-magnitude form. X and Y…
2019
Consider Z = X – Y, where X, Y and Z are all in sign-magnitude form. X and Y are each represented in 𝑛 bits. To avoid overflow, the representation of Z would require a minimum of:
- A.
𝑛 bits
- B.
𝑛 − 1 bits
- C.
𝑛 + 1 bits
- D.
𝑛 + 2 bits
Attempted by 955 students.
Show answer & explanation
Correct answer: C
Key idea: sign-magnitude representation uses one sign bit plus magnitude bits.
Each n-bit number has 1 sign bit and n-1 magnitude bits, so the maximum magnitude representable is 2^{n-1} - 1.
Worst-case subtraction occurs when subtracting the negative maximum from the positive maximum: (2^{n-1}-1) - (-(2^{n-1}-1)) = 2*(2^{n-1}-1) = 2^n - 2.
To represent a magnitude up to 2^n - 2 you need m magnitude bits with 2^m - 1 >= 2^n - 2. Choosing m = n gives 2^n - 1, which is sufficient.
Conclusion: a minimum of n + 1 bits (n magnitude bits plus 1 sign bit) is required to avoid overflow.
A video solution is available for this question — log in and enroll to watch it.