title: How does ThreadLocalRandom.nextLong(long n) work?
body: <p>This is the <a href="http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/concurrent/ThreadLocalRandom.java" rel="nofollow noreferrer">code</a> I don't understand:</p>
  <pre><code>// Divide n by two until small enough for nextInt. On each
  // iteration (at most 31 of them but usually much less),
  </code></pre>
  <p>What? With my trivial <a href="https://dl.dropboxusercontent.com/u/4971686/published/maaartin/so/ThreadLocalRandomDemo.java" rel="nofollow noreferrer">simulation</a> for a randomly chosen <code>n</code> I get up to <code>32</code> iterations and <code>31</code> is the average.</p>
  <pre><code>// 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).
  </code></pre>
  <p>This makes sense.</p>
  <pre><code>long offset = 0;
  while (n &gt;= Integer.MAX_VALUE) {
      int bits = next(2);
  </code></pre>
  <p>Get two bits for the two decisions, makes sense.</p>
  <pre><code>    long half = n &gt;&gt;&gt; 1;
      long nextn = ((bits &amp; 2) == 0) ? half : n - half;
  </code></pre>
  <p>Here, <code>n</code> is <code>n/2.0</code> rounded up or down, nice.</p>
  <pre><code>    if ((bits &amp; 1) == 0) offset += n - nextn;
      n = nextn;
  </code></pre>
  <p>I'm lost.</p>
  <pre><code>}
  return offset + nextInt((int) n);
  </code></pre>
  <p>I can see that it generates a properly sized number, but it looks pretty complicated and rather slow and I definitely can't see why the result should be uniformly distributed.<sup>1</sup></p>
  <hr />
  <p><sup>1</sup>It can't be really uniformly distributed as the state is 48 bits only, so it can generate no more than 2**48 different numbers. The vast majority of <code>long</code>s can't be generated, but an experiment showing it would probably take years.</p>