GATE CS 2019 Q8 — Number Representations (Fixed and Floating Point)

In an $n$-bit sign-magnitude representation:

• $1$ bit is used for the sign.
• $n-1$ bits are used for the magnitude.

The maximum magnitude that can be represented is $2^{n-1} - 1$. Therefore, the range of values for $X$ and $Y$ is:

$$- (2^{n-1} - 1) \le X, Y \le 2^{n-1} - 1$$

To find the range of $Z = X - Y$:

• Maximum value of $Z$: Occurs when $X$ is maximum and $Y$ is minimum: $$Z_{\text{max}} = (2^{n-1} - 1) - (-(2^{n-1} - 1)) = 2(2^{n-1} - 1) = 2^n - 2$$
• Minimum value of $Z$: Occurs when $X$ is minimum and $Y$ is maximum: $$Z_{\text{min}} = -(2^{n-1} - 1) - (2^{n-1} - 1) = -2^n + 2$$

Thus, the maximum magnitude of $Z$ that needs to be represented is $2^n - 2$.

Let $k$ be the number of bits required to represent $Z$ in sign-magnitude form. The maximum magnitude representable with $k$ bits is $2^{k-1} - 1$. To avoid overflow, we must satisfy:

$$2^{k-1} - 1 \ge 2^n - 2 \implies 2^{k-1} \ge 2^n - 1$$

For any integer $n \ge 1$, the smallest integer $k$ that satisfies this inequality is:

$$k = n + 1$$

Example:

Let $n = 3$. The range of $X$ and $Y$ is $[-3, 3]$.

The range of $Z = X - Y$ is $[-6, 6]$.

To represent the magnitude $6$ in binary, we need $3$ bits ($110_2$). Adding $1$ sign bit, we require a minimum of $4$ bits, which is $n+1$ bits.