Почему 2 ^ 31 не делится?
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?Я полагаю, какая-то магия двоичного деления, переполнение, которое нарушает равномерное распределение?
Спасибо!