java.util.Random.Nextint的实现

Question

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的幂的情况？只是为了表现吗？
2. 它为什么拒绝位-val+(n-1)<0数字？

Answer 1

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

int x = rand.nextInt() % n;

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

例如，让我们假设nextint()生成一个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记录了这种行为：

在前面的描述中使用对冲“近似地”仅仅是因为下一个方法仅仅近似地是独立选择的比特的无偏置源。如果它是随机选择比特的完美源，那么所示的算法将以完美的一致性从所述范围中选择int值。

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

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

重点是我的。