java.util.Random.nextInt的实现

Question

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

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

next生成随机位.

1. 当n幂为2时,只需通过生成随机位就可以生成该范围内的随机整数(我假设始终生成31并抛出一些是为了再现性).这段代码路径更简单,我想这是一个更常用的案例,所以值得为这种情况制作一个特殊的"快速路径".

2. 当n不是2的幂时,它会丢弃范围"顶部"的数字,以便随机数均匀分布.例如,想象我们有n=3,并想象我们使用3位而不是31位.那么bits是0到7之间随机生成的数字.如何在那里生成一个公平的随机数？答案:如果bits是6或7,我们扔掉它并生成一个新的.

Answer 2

它这样做是为了确保在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是2的幂的情况:它从底层伪随机数发生器返回正确数量的高阶位.在没有特殊处理的情况下,将返回正确数量的低位.已知诸如由该类实现的线性同余伪随机数发生器在其低阶位的值序列中具有短周期.因此,如果n是2的小幂,则这种特殊情况极大地增加了由连续调用此方法返回的值序列的长度.

重点是我的.