0
$\begingroup$

What is the probability, given a $n$-bit number $x$, that $x$ is greater than or equal to another unkown unsigned uniformly distributed $n$-bit random number $y$ ?

$\endgroup$
  • 1
    $\begingroup$ Do you mean $\mod 2^{32}$? $\mod 32$ means that only bits 0 to 4 need to be examined, so knowing $x_{31}$ to $x_{16}$ is not helpful. $\endgroup$ – Χpẘ Jun 9 '17 at 16:56
  • $\begingroup$ @Χpẘ Indeed you are right, I will edit this! Thanks $\endgroup$ – Raoul722 Jun 9 '17 at 16:57
  • 1
    $\begingroup$ Just to clarify (and hopefully simplify), you are asking that given a 16 bit unsigned number ($x_{15}x_{14}\dots x_0$), what is the probability that it is greater than or equal to another unknown unsigned uniformly distributed random number ($y_{15}y_{14}\dots y_0$) $\endgroup$ – Χpẘ Jun 9 '17 at 17:06
  • $\begingroup$ @Χpẘ Well... Indeed it sounds more clear that way ;-) I will edit my question again then $\endgroup$ – Raoul722 Jun 9 '17 at 17:13
1
$\begingroup$

The probability is $\frac{x_{15}x_{14}\dots x_0 + 1}{65536}$. Since dividing by 64k is a right shift the probability is the number with the binary point (analogous to decimal point) to the left of $x_{15}x_{14}\dots x_0 + 1$, with the exception that if $x_{15}x_{14}\dots x_0 = 0xFFFF$ the probability is 1

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.