edited by
3,467 views
5 votes
5 votes
If A and B are 4 bit Binary numbers given to a 4 bit comparator, then the number of combinations for which A > B is _______.

(A) 120

(B) 160

(C) 116

(D) 140
edited by

1 Answer

Best answer
4 votes
4 votes

There is no need to remember any formulas.

This is a question of Discrete Maths.

Consider this simple question:

Q: How many pairs of single-digit positive integers (A, B) are there such that A > B.

Solution: 

A and B can have values between 1 and 9 (both inclusive).

For A = 1, no value of B satisfies the given condition.

For A = 2, we can have B = 1, i.e one value.

For A = 3, we can have B = 1, 2, i.e 2 values.

...

For A = 9, we can have B = 1, 2, ..., 8, i.e. 8 values.

You can see that summing these will give the answer. This is the summation of first 8 natural numbers. 

Why we get 8? Because A can have any one of the 9 values, where the smallest value makes no value available for B.

Another approach:

Total number of ordered pairs possible (A, B) = $n^2$

Out of these $n^2$ pairs, $n$ pairs will be of equal numbers, i.e. A = B.

when n = 9, we have total pairs = $9^2$, out of these pairs, $9$ pairs are when both number are equal. Like (1, 1), (2, 2), ..., (9, 9).

So, now we are left with $n^2 - n$ pairs of unequal numbers. Out of these exactly half will be such that A > B and another half will be A < B. So, this gives us $(n^2 - n)/2$, or $n(n-1)/2$, i.e. summation of first $n-1$ natural numbers.


Now getting to your question, Suppose we are given $n$ bits. Total possibilities for any number = $2^n$. From the above argument, total number of possible pairs such that A > B is the summation of $2^n - 1$.

$\ \ = \frac {(2^n - 1)2^n}{2}$

$\ \ = \frac {2^{2n} - 2^n}{2}$

This gives your formula.

Answer is: $\ \ = \frac {2^{8} - 2^4}{2}$ = 120

selected by

Related questions

0 votes
0 votes
2 answers
2
rajveer43 asked Jan 12
178 views
The number of full and half-adders required to add $32$-bit numbers is______________________
0 votes
0 votes
0 answers
3
Redcom1988 asked Dec 23, 2023
176 views
Design a counter according to the state diagram above using only NAND gates and JK Flip-flops (if needed) complete with state tables
0 votes
0 votes
0 answers
4