为什么2 ^ 31不能被n整除？ [英] Why 2^31 is not divisible by n?

问题描述

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.

The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2^31 is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2^30+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.

算法：

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

代码测试 n>的情况2 ^ 30 和位> Ñ。然后设置最高有效位并将条件中的结果转换为负值。

The code tests the case where n > 2^30 and bits > n. Then the most significant bit is set and turns the result in the condition into negative one.

据我所知位最多 2 ^ 31-1 =>有50％的概率。 位可以是< 2 ^ 30或介于2 ^ 30和2 ^ 31之间

I understand that bits is at most 2^31-1 => there is the 50% probability. The bits can be either < 2^30 or between 2^30 and 2^31

无论如何，

1. 为什么 2 ^ 31不能被n 整除？


2. 为什么只有两个数字> 2 ^ 30时才有效？

1. Why 2^31 is not divisible by n?
2. Why is it effective only when both numbers > 2^30?

我猜一些二元分裂法术，一个破坏统一分布的溢出？

I guess some binary division magic, an overflow which breaks the uniform distribution?

谢谢！

推荐答案

这是一个问题，因为任何时候你想要生成一个较小范围内的随机数一个在较大范围内，较小范围的大小不能被较大范围的整数整除。

This is a problem caused any time you want to generate a random number in a smaller range from one in a larger range where the size of the smaller range isn't divisible by the size of the larger.

如果你有一个0到9之间的随机数（包括0和9）并且想要将它改为0到3之间的一个，如果你只是将这个简单地做为n％4，你有3/10的机会获得0（0,4或8）％4，但是2 / 10获得3（3或7）％4的机会。这里最简单的方法是重新生成随机数，如果它大于7。

If you had a random number between 0 and 9 (inclusive) and wanted to change it to one between 0 and 3, if you just did this trivially as n%4, you'd have a 3/10 chance of getting a 0 (0, 4 or 8)%4, but a 2/10 chance of getting a 3 (3 or 7)%4. The simplest way around this here is to just re-generate the random number if it's greater than 7.

它所讨论的最坏情况是当较小范围的大小时只是大一半的大小的一半，所以你将不得不重新生成超过一半的时间。

The worst case it's talking about is when the size of the smaller range is just over half the size of the larger one, so you'll have to re-generate just over half of the time.

这篇关于为什么2 ^ 31不能被n整除？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！