java - java.util.Random.nextInt 的实现

Question

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

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;
}

我的问题是:

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

Answer 1

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

int x = rand.nextInt() % n;

但这会改变值的分布，除非 n 是 2^31 的约数，即 2 的幂。这是因为模运算符会产生大小不是一样。

例如，假设 nextInt() 生成一个介于 0 和 6 之间的整数(含 0 和 6)，而您想绘制 0,1 或 2。很简单，对吧？

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记录此行为:

The hedge "approximately" is used in the foregoing description only because the next method is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm shown would choose int values from the stated range with perfect uniformity.

The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2^31 is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2^30+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.

The algorithm treats the case where n is a power of two specially: it returns the correct number of high-order bits from the underlying pseudo-random number generator. In the absence of special treatment, the correct number of low-order bits would be returned. Linear congruential pseudo-random number generators such as the one implemented by this class are known to have short periods in the sequence of values of their low-order bits. Thus, this special case greatly increases the length of the sequence of values returned by successive calls to this method if n is a small power of two.

重点是我的。