java - ThreadLocalRandom.nextLong(long n)如何工作？

Question

这是我不明白的code:

// Divide n by two until small enough for nextInt. On each
// iteration (at most 31 of them but usually much less),

什么？对于随机选择的 n，我使用琐碎的 simulation进行 32迭代，而 31是平均值。

// randomly choose both whether to include high bit in result
// (offset) and whether to continue with the lower vs upper
// half (which makes a difference only if odd).

这很有道理。

long offset = 0;
while (n >= Integer.MAX_VALUE) {
    int bits = next(2);

为这两个决定获取两位，这是有道理的。

    long half = n >>> 1;
    long nextn = ((bits & 2) == 0) ? half : n - half;

在这里， n是向上或向下四舍五入的 n/2.0，很好。

    if ((bits & 1) == 0) offset += n - nextn;
    n = nextn;

我迷路了。

}
return offset + nextInt((int) n);

我可以看到它生成了一个适当大小的数字，但是它看起来相当复杂且相当慢，而且我绝对不明白为什么结果应该均匀分布。1

1由于状态仅为48位，因此无法真正均匀地分布，因此它最多可以生成2 ** 48个不同的数字。绝大多数 long不能生成，但是显示它的实验可能要花费数年时间。

Answer 1

我认为您可能会误会...。让我尝试用我看待它的方式来描述算法:

首先，假设nextInt(big)(nextInt，不是nextLong)能够正确生成0(含)和big(不含)之间的良好分布值。

此nextInt(int)函数用作nextLong(long)的一部分

因此，该算法通过循环工作直到该值小于Integer.MAX_INT为止，此时它使用nextInt(int)。更有趣的是在那之前它做了什么...

在数学上，如果我们取一个数字的一​​半，则将其减去一半，然后再减去一半，再减去一半，依此类推，如此反复，那么它将趋于零。同样，如果取一个数字的一​​半，然后将其加到一半的一半，以此类推，那么它将趋向于原始数字。

该算法在这里所做的是只占用一半的数字。通过整数除法，如果数字为奇数，则有一个“大”一半和一个“小”一半。算法“随机地”选择那些一半(大或小)之一。

然后，它随机选择添加一半或不添加一半到输出。

它会将数字减半，并(可能)将一半相加，直到一半小于Integer.MAX_INT。那时，它只计算nextInt(half)值并将其添加到结果中。

假设初始长限制远大于Integer.MAX_VALUE，那么最终结果将获得nextInt(int)的所有好处，因为它具有一个较大的int值，该int值至少为状态的32位，对于所有较高位为2位的状态在Integer.MAX_VALUE之上。

原始限制越大(距离Long.MAX_VALUE越近)，循环迭代的次数就越多。在最坏的情况下，它将经历32次，但对于较小的限制，它将经历较少的时间。在最坏的情况下，对于很大的限制，您将获得用于循环的64位随机性，然后nextInt(half)也需要任何随机性。

编辑:WalkThrough添加了-确定结果的数量比较困难，但是从0到Long.MAX_VALUE - 1的long的所有值都是可能的结果。使用nextLong(0x4000000000000000)作为“证明”是一个很好的示例，因为所有减半过程将是偶数，并且它设置了63位。

因为设置了位63(因为位64会使数字为负，所以是最高有效位，这是非法的)，这意味着我们将值减半32次，直到值<= Integer.MAX_VALUE(即0x000000007fffffff-和half)当我们到达那里时将是0x0000000004000000。因为减半和移位是相同的过程，所以它认为要进行的减半与最高位集和第31位之间的差一样多。63-31为32，因此我们将减半32倍，因此我们将32减半在while循环中循环。 0x4000000000000000的初始起始值意味着当我们将值减半时，一半将只设置一位，并且它将“沿行”该值-每次在循环中向右移1。

因为我仔细选择了初始值，所以很明显，在while循环中，逻辑本质上是在决定是否设置每个位。它采用输入值的一半(即0x2000000000000000)，并决定是否将其添加到结果中。为了便于讨论，我们假设所有循环都决定将一半添加到偏移量，在这种情况下，我们从偏移量0x0000000000000000开始，然后每次循环都添加一半，这意味着每次添加:

0x2000000000000000
0x1000000000000000
0x0800000000000000
0x0400000000000000
.......
0x0000000100000000
0x0000000080000000
0x0000000040000000  (this is added because it is the last 'half' calculated)

在这一点上，我们的循环运行了32次，它已“选择”将值相加32次，因此该值中至少包含32个状态(如果计算大/小半决定则为64个状态)。现在，实际偏移量为 0x3fffffffc0000000(设置了从62到31的所有位)。

然后，我们调用nextInt(0x40000000)，这很幸运，它使用31位状态到达那里，产生结果0x3fffffff。我们将此值添加到偏移量中并得到结果:

0x3fffffffffffffff

有了完美的 nextInt(0x40000000)结果分布，我们就可以完美地覆盖 0x7fffffffc0000000到 0x3fffffffffffffff的值，而不会出现间隙。在while循环中具有完美随机性的情况下，我们的高位本应该是 0x0000000000000000到 0x3fffffffc0000000的完美分布结合起来，从0到我们的 0x4000000000000000极限(不包括)都具有完全覆盖范围

使用高位的32位状态和 nextInt(0x40000000)的(假定的)最少31位状态，我们可以得到63位的状态(如果算上大/小半决定，则更多)，并且具有完整的覆盖范围。