java.util.Random.nextInt 的实现

random java

2022-09-03 14:04:17

此函数来自 java.util.Random。它返回一个在和给定之间均匀分布的伪随机数。不幸的是，我没有得到它。int0n

public int nextInt(int n) {
    if (n <= 0)
        throw new IllegalArgumentException("n must be positive");

    if ((n & -n) == n)  // i.e., n is a power of 2
        return (int)((n * (long)next(31)) >> 31);

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

我的问题是：

为什么它特别处理二的幂的情况？只是为了性能吗？n
为什么它拒绝数字？bits - val + (n-1) < 0

答案 1

它这样做是为了确保值在和之间均匀分布。你可能会想做这样的事情：0n

int x = rand.nextInt() % n;

但这会改变值的分布，除非 n 是的除数，即 2 的幂。这是因为模运算符将生成大小不相同的等价类。2^31

例如，假设生成一个介于 0 和 6 之间的整数（包括 0 和 6），并且您想要绘制 0、1 或 2。很简单，对吧？nextInt()

int x = rand.nextInt() % 3;

不。让我们看看为什么：

0 % 3 = 0
1 % 3 = 1
2 % 3 = 2
3 % 3 = 0
4 % 3 = 1
5 % 3 = 2
6 % 3 = 0

因此，您有 3 个值映射到 0，只有 2 个值映射到 1 和 2。您现在有偏差，因为 0 比 1 或 2 更有可能返回。

与往常一样，javadoc 记录了以下行为：

在前面的描述中使用了“近似”的对冲，只是因为下一种方法只是独立选择位的近似无偏源。如果它是随机选择位的完美源，则显示的算法将从具有完美均匀性的规定范围中选择int值。

该算法有点棘手。它拒绝会导致分布不均匀的值（由于 2^31 不能被 n 整除）。值被拒绝的概率取决于 n。最坏的情况是 n=2^30+1，其拒绝的概率为 1/2，循环终止前的预期迭代次数为 2。

该算法特别处理 n 是 2 的幂的情况：它从底层伪随机数生成器返回正确数量的高阶位。在没有特殊处理的情况下，将返回正确数量的低阶位。线性同余伪随机数生成器（例如此类实现的生成器）已知在其低阶位的值序列中具有较短的周期。因此，如果 n 是 2 的小幂，则此特殊情况会大大增加连续调用此方法返回的值序列的长度。

重点是我的。

答案 2

next生成随机位。

当是2的幂时，该范围内的随机整数可以通过生成随机位来生成（我假设总是生成31并丢弃一些是为了可重复性）。这个代码路径更简单，我想这是一个更常用的情况，所以值得为这种情况做一个特殊的“快速路径”。n
当不是 2 的幂时，它会丢弃范围“顶部”处的数字，以便随机数均匀分布。例如，想象我们有，想象我们使用3位而不是31位。因此，是一个介于 0 和 7 之间的随机生成的数字。如何在那里生成一个公平的随机数？答：如果是6或7，我们把它扔掉并生成一个新的。nn=3bitsbits