GATE CS 2019 Q.18 (CS Q.8): Number Representations and Computer Arithmetic

Consider $Z = X - Y$ , where $X, Y$ and $Z$ are all in sign-magnitude form. $X$ and $Y$ are each represented in $n$ bits. To avoid overflow, the representation of $Z$ would require a minimum of:

$n$ bits

$n - 1$ bits

$n + 1$ bits

$n + 2$ bits

Official answer and solution

Official answer: C
From: Official GATE 2019 answer key

Solution

Find the range of values of the difference Z = X - Y in sign-magnitude representation and determine the minimum number of bits needed to represent it without overflow.

In an $n$ -bit sign-magnitude representation, $1$ bit is used for the sign and $n-1$ bits are used for the magnitude. The range of representable numbers is:

-[2^{n-1} - 1, 2^{n-1} - 1]

Let $X, Y \in [-(2^{n-1} - 1), 2^{n-1} - 1]$ . The maximum possible value of $Z = X - Y$ occurs when $X = 2^{n-1} - 1$ and $Y = -(2^{n-1} - 1)$ :

Z_{\max} = (2^{n-1} - 1) - (-(2^{n-1} - 1)) = 2(2^{n-1} - 1) = 2^n - 2

Similarly, the minimum possible value is:

Z_{\min} = -(2^{n-1} - 1) - (2^{n-1} - 1) = -(2^n - 2)

To represent a magnitude as large as $2^n - 2$ in sign-magnitude form:

2^m - 1 \ge 2^n - 2 \implies 2^m > 2^n - 1 \implies m \ge n

Thus, the magnitude requires at least $n$ bits. Adding $1$ bit for the sign gives a total of $n + 1$ bits.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2019 Computer Science and Information Technology (CS)
Question: 18 of 65, printed as CS Q.8
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source