http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt%28int%29 говорит:

Алгоритм немного хитрый. Он отклоняет значения, которые могут привести к неравномерному распределению (из-за того, что 2 ^ 31 не делится на n). Вероятность отклонения значения зависит от n. Худший случай - это n = 2 ^ 30 + 1, для которого вероятность отклонения равна 1/2, а ожидаемое количество итераций до завершения цикла равно 2.

Алгоритм:

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

Код тестирует случай, когдаn > 2^30 а такжеbits > n, Затем устанавливается старший значащий бит, который превращает результат в условии в отрицательный.

Я это понимаюbits самое большее2^31-1 => есть вероятность 50%.bits может быть <2 ^ 30 или от 2 ^ 30 до 2 ^ 31

Так или иначе,

Почему2 ^ 31 не делится?Почему он эффективен только тогда, когда оба числа> 2 ^ 30?

Я полагаю, какое-то магическое двоичное деление, переполнение, которое нарушает равномерное распределение

Спасибо!