ThreadLocalRandom.NextLong（long n）如何工作？

Question

这是我不懂的代码：

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

什么？通过对随机选择的n进行简单的模拟，我得到了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;

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

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

Answer 1

我觉得你有点搞错了...让我试着以我所看到的方式来描述算法：

首先，假设nextInt(big)(nextInt，不是nextLong)能够正确地生成0（包括）和big（不包括）之间分布良好的值范围。

此NextInt(int)函数用作NextLong(long)的一部分

从数学上讲，如果我们取一个数的一半，减去一半，再减去一半，再减去一半，等等，我们这样做的次数足够多，它会趋于零。同样，如果你取一个数的一半，然后把它加到一半的一半上，等等，它就会倾向于原来的数。

算法在这里做的是它需要一半的数字。通过做整数除法，如果数字是奇数，那么就有一个‘大’的一半和一个‘小’的一半。算法“随机”地选择其中一个（大的或小的）。

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

编辑：已添加演练-计算结果的数量较难，但从0到long.max_value-1的所有long值都是可能的结果。作为“证明”，使用nextlong(0x400000000000000000)是一个简单的示例，因为所有的减半过程都是偶数的，并且它设置了63位。

由于位63被设置（这是可用的最高有效位，因为位64会使数字为负数，这是非法的），这意味着在值为<=integer.max_value之前，我们将值减半32次（这是0x000000007FFFFFF-当我们到达那里时，我们的半将为0x0000000004000000)。因为减半和位移位是相同的过程，所以它认为要做的减半与最高位组和位31之间的差值一样多。63-31是32，所以我们将事物减半32倍，因此我们在while循环中执行32个循环。0x400000000000000000的初始起始值意味着，当我们将该值减半时，在这一半中只设置了一个位，并且它将沿着值“走”下去--每次通过循环时将1向右移动。

因为我谨慎地选择了初始值，所以很明显，在while循环中，逻辑实际上是在决定是否设置每个位。它接受输入值的一半（即0x200000000000000000)，并决定是否将其添加到结果中。为了论证起见，我们假设所有的循环都决定在偏移量上加上一半，在这种情况下，我们从偏移量

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

在这一点上，我们的循环已经运行了32次，它已经“选择”添加值32次，因此在值中至少有32个状态（如果计算大/小半决定，则为64）。实际失调现在为0x3FFFFFFFC0000000（从62到31的所有位均置1）。

然后，我们调用nextInt(0x40000000)，幸运的是，它会产生结果0x3FFFFFFFF，使用31位状态来实现。我们将这个值添加到我们的偏移量中，得到的结果是：

0x3fffffffffffffff

如果nextint(0x40000000)结果的“完美”分布，我们就可以完美地覆盖0x7FFFFFFFFC0000000到0x3FFFFFFFFFFFFFFFFFFFFFFFF的值，没有任何间隙。如果我们的while循环具有完美的随机性，我们的高位将会是0x0000000000000000到0x3FFFFFFC0000000的完美分布，这样就可以完全覆盖从0到0x40000000000000000的极限（不包括）

使用来自高位的32位状态，以及来自nextint(0x40000000)的（假定）最小31位状态，我们有63位状态（如果计算大半/小半决策，则更多），并且完全覆盖。