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

Question

算法有点棘手。它拒绝会导致分布不均匀的值（因为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的情况。然后设置最高有效位，并将条件中的结果变为负值。

null

Answer 1

这是一个问题，只要你想从一个较大范围内的随机数生成一个较小范围内的随机数，其中较小范围的大小不能被较大范围内的大小整除。

如果你有一个0到9（含）之间的随机数，想把它改成0到3之间的随机数，如果你只做了n%4，你有3/10的几率得到0(0，4或8)%4，但有2/10的几率得到3（3或7）%4。最简单的方法就是重新生成大于7的随机数。

最糟糕的情况是，小范围的大小是大范围的一半多一点，所以你必须重新生成一半多一点的时间。