mercredi 18 mars 2015

Confusing implementation of java.util.Random nextInt(int n)

I am trying to understand how java.util.Random.nextInt(int n) works and despite all the search and even debugging cannot completely understand the implementation.


It is the while loop that causes confusion: http://ift.tt/1bg7AAs



int bits, val;
do {
bits = next(31);
val = bits % n;
} while (bits - val + (n-1) < 0);


I realize this is supposed to address the modulo bias, but struggling to see how.


Question: how can possibly the expression



bits - val + (n-1)


be negative given that bits value is 31 bit long, i.e. bits is always positive? If bits is positive, val is always less than bits then while condition always stays > 0...





Aucun commentaire:

Enregistrer un commentaire