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

To find the probability that two independently and uniformly chosen numbers from the set $\{1, 2, \ldots, 13\}$ have the same most significant bit (MSB) in their 4-bit unsigned binary representation, we first determine the MSB of each number.

The 4-bit binary representations of the numbers from $1$ to $13$ are:

• MSB = 0:
  • $1 = 0001_2$
  • $2 = 0010_2$
  • $3 = 0011_2$
  • $4 = 0100_2$
  • $5 = 0101_2$
  • $6 = 0110_2$
  • $7 = 0111_2$
  There are $n_0 = 7$ numbers with $\text{MSB} = 0$.
• MSB = 1:
  • $8 = 1000_2$
  • $9 = 1001_2$
  • $10 = 1010_2$
  • $11 = 1011_2$
  • $12 = 1100_2$
  • $13 = 1101_2$
  There are $n_1 = 6$ numbers with $\text{MSB} = 1$.

Since the two numbers are chosen independently and with replacement, the total number of possible outcomes is:

The favorable outcomes are those where both numbers have the same MSB:

1. Both numbers have $\text{MSB} = 0$: $7 \times 7 = 49$ ways
2. Both numbers have $\text{MSB} = 1$: $6 \times 6 = 36$ ways

Thus, the total number of favorable outcomes is:

The required probability is:

Rounding off to $3$ decimal places, we get $0.503$.