http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt%28int%29 mówi:

Algorytm jest nieco skomplikowany. Odrzuca wartości, które skutkowałyby nierównym rozkładem (ze względu na fakt, że 2 ^ 31 nie jest podzielne przez n). Prawdopodobieństwo odrzucenia wartości zależy od n. Najgorszym przypadkiem jest n = 2 ^ 30 + 1, dla którego prawdopodobieństwo odrzucenia wynosi 1/2, a oczekiwana liczba iteracji przed zakończeniem pętli wynosi 2.

Algorytm:

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

Kod sprawdza przypadek, w którymn > 2^30 ibits > n. Następnie ustawia się najbardziej znaczący bit i zamienia wynik w warunek na ujemny.

Rozumiem, żebits jest najwyżej2^31-1 => istnieje prawdopodobieństwo 50%. Thebits może być <2 ^ 30 lub między 2 ^ 30 i 2 ^ 31

Tak czy inaczej,

Czemu2 ^ 31 nie jest podzielne przez n?Dlaczego działa tylko wtedy, gdy obie liczby> 2 ^ 30?

Domyślam się, że jakaś magia podziału binarnego, przepełnienie, które łamie rozkład jednorodny?

Dziękuję Ci!