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

您的计算中缺少 n 的值。 n 是负数，bits - val -1 1 < n 或者 N 大到足以使整数溢出并变成负数。

Answer 2

问题已在 implementation-of-java-util-random-nextint.

中得到解决

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

数学上我们检查：

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

如果 java 有无符号的 32 位整数算术，就可以按原样写。