GATE CSE 2016 Set 2 | Question: 09

Question

Let $X$ be the number of distinct $16$-bit integers in $2's$ complement representation. Let $Y$ be the number of distinct $16$-bit integers in sign magnitude representation Then $X - Y$ is______.

Comments

This difference of 1 is due to the unique representation of zero in 2's complement

Answer 1

2's Complement Representation

The range of $n\text{-bit}\; 2$'s Complement Numbers is $-(2^{n-1})$ to $+(2^{n-1}-1)$

For example, if $n = 2$, then $-2, -1, 0, 1$ belong to the range(which are distinct)

In general $2^{n}$ distinct integers are possible with $n\text{-bit}\;2's$ Complement Number $\to X$

Sign Magnitude Representation

The range of $n\text{-bit}$ Sign Magnitude numbers is $- (2^{n-1}-1)$ to $+ (2^{n-1}-1)$

For example, if $n = 2$, then $-1, -0, +0, +1$ belong to the range in which $-0 = +0$ and both represent zero.

In general $2^{n}-1$ distinct integers are possible with $n\text{-bit}$ Sign magnitude representation $\to Y$

$X-Y =2^{n} - (2^{n}-1) =1.$

Comments

Nice Explanation!

---

This difference of 1 is due to the unique representation of zero in 2's complement.

---

@harsh

I think it is because we can write -8 = 1000 in 2’s complement instead of 11000.

-0 and +0 are anyway being counted just as one unique integer because of the statement ‘distinct 16-bit integers’.

---

Next question :

$X$ = number of distinct $n$ bit integers in $2's$ complement representation,

$Y$ = number of distinct $n$ bit integers in $1's$ complement representation,

$Z$ = number of distinct $n$ bit integers in Sign Magnitude representation

Relation between $X,Y$ and $Z$ ?

$Y = Z$, $X = 1 + Y$, $X = 1 + Z$

Both $1's$ complement and Sign Magnitude representation have two representations for $0$ but $2's$ complement representation have only one representation for $0$.

If we represent $1's$ complement numbers on number line, then in $2's$ complement representation, we shift all the negative numbers represented by $1's$ complement representation to one postion left on the number line and for $-1$ we give all one's which was earlier the representation of $0$ in case of $1's$ complement.

Answer 2

For N bits, Distinct values represented in 2's complement is -2^n-1 to 2^n-1 -1

Distinct values represented in Signed Magnitude is -(2^n-1 -1) to 2^n-1 -1

Difference is 1.

Comments

It implies that there are more representation in signed bit(Y) than 2s complemented form(X)

X-Y=-1

---

The only difference between sign magnitude and 2's complement representation is that sign magnitude has 2 representations for zero whereas latter has only 1. I think ans should be -1

---

There are two representations of zero in sign magnitude i.e +0 and -0 while there is distinct representation of zero in 2's complement. So, the difference is 1.

---

Range of signed magnitude representation = $-2^{n-1}-1$ to $2^{n-1}-1$

Total numbers in this range = $2^{n-1}-1-(-2^{n-1}-1)+1$

                                              =$2^{n-1}+2^{n-1}+1$

                                              =$2^n+1$

why am i getting $2^n+1$ instead of $2^n-1$

Answer 3

For N bits, Distinct values represented in 2's complement is -2^n-1 to 2^n-1 -1 

So the total distinct value is (2ⁿ) => Represented by  X 

Distinct values represented in Signed Magnitude is -(2^n-1 -1) to 2^n-1 -1 

So the total distinct value is (2ⁿ-1) => Represented by  Y

X - Y = (2ⁿ) - (2ⁿ-1) = 1 ANS

Answer 4

2's complement has one representation for 0 while signed magnitude has 2 representations for 0.

So answer is 2-1 = 1.

Comments

Good ,,