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

Question

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);

代码测试了 wheren > 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 的随机数。

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

Answer 2

2^31 只能被一个幂或 2 整除。当您检查代码时，这种特殊情况将单独处理，无需循环。描述与拒绝过程有关，n 不是 2 的幂。

Answer 3

关于第一个问题：

据我理解这句话，据说当 2^31 不能被 n 整除时会导致不均匀分布。

对不起，我不知道第二个问题。