java - 令人困惑的 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)

如果 bits 值是 31 位长，则为负数，即 bits 始终为正数？如果 bits 为正，val 总是小于 bits 那么 while 条件总是保持 > 0...

Answer 1

该问题已在 implementation-of-java-util-random-nextint. 中得到解决。

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

数学上我们检查:

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

如果 java 具有无符号 32 位整数算术，则可以按原样编写它。