http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt%28int%29说:
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
和 bits > n
的情况。然后设置最高有效位并将条件中的结果变为负数。
我知道 bits
最多是 2^31-1
=> 有 50% 的概率。 bits
可以是 < 2^30 或 2^30 和 2^31 之间
无论如何,
- 为什么 2^31 不能被 n 整除?
- 为什么只有当两个数字都> 2^30 时才有效?
我猜是一些二进制除法魔法,一个破坏均匀分布的溢出?
谢谢!
最佳答案
每当您想从较大范围内的随机数生成较小范围内的随机数时,都会出现此问题,其中较小范围的大小不能被较大范围的大小整除。
如果你有一个介于 0 和 9(含)之间的随机数,并想将其更改为介于 0 和 3 之间的一个数,如果你只是简单地将其设置为 n%4,你将有 3/10 的机会获得0(0、4 或 8)%4,但有 2/10 的机会获得 3(3 或 7)%4。解决此问题的最简单方法是,如果随机数大于 7,则重新生成随机数。
它所说的最坏情况是当较小范围的大小刚刚超过较大范围的一半时,因此您将不得不重新生成刚好超过一半的时间。
关于java - 为什么 2^31 不能被 n 整除?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19929894/