java.util.Random.nextInt的实现
该函数来自java.util.Random 。 它返回一个在0和给定n之间均匀分布的伪随机int 。 不幸的是我没有得到它。
public int nextInt(int n) { if (n > 31); int bits, val; do { bits = next(31); val = bits % n; } while (bits - val + (n-1) < 0); return val; }
我的问题是：
- 为什么它特别处理
n是2的幂的情况？ 这仅仅是为了表现吗？ - 为什么它会拒绝
bits - val + (n-1) < 0？
next生成随机位 。
-
当
n是2的幂时，仅通过生成随机位就可以生成该范围内的随机整数（我假设总是产生31并且抛弃一些是为了再现性）。 这段代码路径更简单，我想这是一个更常用的案例，所以值得为这种情况制作一个特殊的“快速路径”。 -
当
n不是2的幂时，它会丢弃范围“顶部”的数字，以便随机数均匀分布。 例如，假设我们有n=3，并想象我们使用的是3位而不是31位。 所以bits是0到7之间随机生成的数字。如何在那里生成一个公平的随机数？ 答案：如果bits是6或7，我们将它丢弃并生成一个新的。
它这样做是为了确保0和n之间的值的均匀分布。 你可能想做类似的事情：
int x = rand.nextInt() % n;
但这会改变值的分布，除非n是2^31的除数，即2^31的幂。这是因为模运算符会产生大小不同的等价类。
例如，假设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的小幂，则这种特殊情况极大地增加了由连续调用此方法返回的值序列的长度。
重点是我的。