Сложная реализация java.util.Random nextInt (int n)

Question

Я пытаюсь понять, как java.util.Random.nextInt (int n) работает и, несмотря на все поиски и даже отладки, не может полностью понять реализацию.

Это в то время как цикл, который вызывает путаницу: http://docs.oracle.com/javase/7/docs/api/java/util/Random.html#nextInt(int)

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

Я понимаю, что это, как предполагается рассмотреть смещение по модулю, но изо всех сил, чтобы увидеть, как.

Вопрос: как может возможно выражение

bits - val + (n-1) 

быть отрицательным при условии, что биты значение 31 бит длиной, то есть биты всегда положительна? Если биты положительна, вал всегда меньше, чем биты затем в то время как состояние всегда остается> 0 ...

Answer 1

вопрос был уже рассмотрен в implementation-of-java-util-random-nextint.

В принципе, мы должны отбросить некоторые топ-большинство элементов для bits в диапазоне [0..2^31[, потому что они вызывают неравномерное распределение

Математически мы проверяем:

bits - val + (n-1) >= 2^31 

и мог бы написать его, как если бы у java была неподписанная 32-битная целая арифметика.

Answer 2

Вы упускаете значение n в вашем расчете. Либо n отрицательный, bits - val -1 1 < n, либо иначе N является достаточно большим, чтобы сделать целочисленное переполнение и стать отрицательным числом.