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), 

什麼？隨着我的瑣碎simulation爲隨機選擇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; 

這裏，n爲n/2.0四捨五入，美觀大方。

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

我迷路了。

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

我可以看到，它產生一個適當大小的數字，但它看起來相當複雜和相當慢，我絕對看不出爲什麼結果應該是均勻分佈的。

---

它不能真正均勻分佈作爲狀態是隻有48位，所以它可以產生不超過2 ** 48不同的號碼。絕大多數long s不能生成，但顯示它的實驗可能需要幾年時間。

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）的所有好處，對於至少爲32位狀態的大型int值，以及2位狀態所有高於Integer.MAX_VALUE的高位。

原始限制越大（越接近Long.MAX_VALUE），循環將迭代的次數越多。在最壞的情況下，它會進行32次，但是對於更小的限制，它會經歷更少的次數。在最壞的情況下，對於非常大的限制，您將得到用於循環的64位隨機性，然後對nextInt(half)也需要。

---

編輯：演練添加 - 工作出成果的數量是很難的，但，長期從0到Long.MAX_VALUE - 1所有的值都是可能的結果。作爲使用nextLong(0x4000000000000000)的「證明」是一個很好的例子，因爲所有的減半處理過程都是平穩的，並且它已經被設置了63位。

因爲63位設置（最顯著位可用，因爲bit64將使數負，這是違法的），這意味着我們將前值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），如果幸運的話，它會產生結果0x3fffffff，使用31位狀態到達那裏。我們將此值添加到我們的偏移量並得到結果：

0x3fffffffffffffff 

隨着nextInt(0x40000000)結果的「完美」的分佈，我們會通過0x3fffffffffffffff有值0x7fffffffc0000000的完美覆蓋，無縫隙。隨着while循環完美的隨機性，我們的高比特將已經通過0x3fffffffc0000000聯合的0x0000000000000000一個完美的分佈有從0全覆蓋，通過我們的0x4000000000000000

限制（獨家）與高狀態的32位比特以及來自nextInt(0x40000000)的（假定的）最小31比特狀態，我們有63比特的狀態（如果你計算大/小一半的決定，則比較多）以及全覆蓋。