为什么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);

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

我知道bits最多2^31-1=>有50%的概率.的bits可以是<2 ^ 30或2和2之间^ 30 ^ 31

---

无论如何,

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

我猜一些二元分裂法术,一个破坏均匀分布的溢出？

谢谢!

Answer 1

这是一个问题,任何时候你想要在较大范围内生成一个较小范围内的随机数,其中较小范围的大小不能被较大范围的整数整除.

如果你有一个介于0到9之间的随机数(包括0和9),并希望将它改为0到3之间的一个,如果你只是简单地将其作为n%4,那么你有3/10的机会获得0( 0,4或8)%4,但获得3(3或7)%4的概率为2/10.这里最简单的方法是重新生成随机数,如果它大于7.

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