java - 为什么 2^31 不能被 n 整除？

Question

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 之间

---

无论如何，

1. 为什么 2^31 不能被 n 整除？
2. 为什么只有当两个数字都> 2^30 时才有效？

我猜是一些二进制除法魔法，一个破坏均匀分布的溢出？

谢谢!

Answer 1

每当您想从较大范围内的随机数生成较小范围内的随机数时，都会出现此问题，其中较小范围的大小不能被较大范围的大小整除。

如果你有一个介于 0 和 9(含)之间的随机数，并想将其更改为介于 0 和 3 之间的一个数，如果你只是简单地将其设置为 n%4，你将有 3/10 的机会获得0(0、4 或 8)%4，但有 2/10 的机会获得 3(3 或 7)%4。解决此问题的最简单方法是，如果随机数大于 7，则重新生成随机数。

它所说的最坏情况是当较小范围的大小刚刚超过较大范围的一半时，因此您将不得不重新生成刚好超过一半的时间。