java.util.Random nextInt（int n）的令人困惑的实现

Question

我试图理解java.util.random.NextInt（int n）是如何工作的，尽管进行了所有的搜索甚至调试，但我还是不能完全理解它的实现。

造成混乱的是while循环:http://docs.oracle.com/javase/7/docs/api/java/util/random.html#NextInt(int)

int bits, val;
do {
    bits = next(31);
    val = bits % n;    
} while (bits - val + (n-1) < 0);

我意识到这应该是为了解决模数偏见，但很难看到如何解决。

bits - val + (n-1)

Answer 1

这个问题已经在-java-util-random-nextint的实现中得到了解决。

基本上，我们必须删除[0..2^31[范围内位的一些最上面的元素，因为它们导致非均匀分布

在数学上，我们检查：

bits - val + (n-1) >= 2^31