On this page, we describe the **XORShift** technique for generating medium-quality
random numbers. Like other techniques, XORShift generates higher quality random numbers than the standard
`java.lang.Random` class.
It should be said that as a technique for generating random numbers in Java,
it has been largely
surpassed by the ThreadLocalRandom class since Java 8.
However, the XORSfhit algorithm is worth knowing about as a general programming technique, not least
because you will find it used in other Java source code— including the JDK!

The XORShift technique was proposed by George Marsalia in 2003. It generates random numbers using a single seed and just 3 shifts and XOR operations. It can be used to generate different bit widths, with 32-bit and 64-bit versions being common. The 64-bit XORShift algorithm in Java looks as follows:

long seed = Systen.nanoTime(); public long randomLong() { seed ^= (seed << 21); seed ^= (seed >>> 35); seed ^= (seed << 4); return seed; }

In this example, we use `Systen.nanoTime()` for the initial seed, but any source of *entropy* or "seed randomness" is possible in principle.
As with other generators, we can also start with a known fixed seed if we always want to generate the same predetermined sequence,
e.g. for replicability in unit tests or simulations.

What are the numbers 21, 35 and 4? In fact, different shift values are possible, and the direction of the shifts can also be reversed.
But Marsaglia's mathematical proof shows
that certain combinations of shifts such as (21, 35, 4) will generate a "full" period: the above example will cycle round all 2^{64}-1 possible
non-zero long values. Marsaglia also found that the resulting values from certain shift values pass his
"Diehard battery" of statistical tests for randomness^{1}.
L'Ecuyer & Simard (2007)^{2} also found that values of 13, 7 and 17 fail on only
7 of the 160 tests of their *BigCrush* battery (for comparison, `java.util.Random`
fails on 21, while crypographic generators such as Java's
SecureRandom— as indeed we might expect—
generally pass all tests).

Cryptographic quality random number generators and hashing algorithms also use very simple bitwise operations, such as XOR, addition, bit shifts
and rotations^{3}. So why not simply use SecureRandom, for example?

The advantage of XORShift and similar techniques is a performance/quality tradeoff: `SecureRandom` is typically tens if not hundreds
of times slower than a simpler technique such as XORShift or ThreadLocalRandom, while still being
of high enough quality for many applications.

As mentioned above, if you are looking for a fast but higher quality alternative to the Java `Random` class, then
ThreadLocalRandom is probably the default choice since Java 8. That said,
it is also possible to subclass `java.lang.Random` to use
a different generation technique such as XORShift.

The XORShift algorithm is a vast improvement on LCG generators. However, it does still have at least a couple of weaknesses. These weaknesses can be alleviated by combining XORShift with a secondary generator:

- used "raw", XORShift will never produce the value 0 (the value is clearly outlawed, or the generator would get stuck on zero!); used to produce long values as a sequence of calls, there'll always be one possible value that won't be produced;
- the generator will occasionally go through
**cycles in which few bits are set**in the numbers generated; - other techniques such as the algorithm used in ThreadLocalRandom produce better quality random numbers with better or comparable performance.

On the other hand, due to its simplicity, XORShift still has its place as a quick "inline" random number generation technique.

Needless to say, XORShift on its own is **not cryptographically secure**: it is
relatively trivial for somebody observing a couple of numbers generated to deduce (at worst by trial and error) the
shift values used, and hence predict future numbers.

The most common competitor to XORShift in Java is the ThreadLocalRandom class. The SplittableRandom class will also be appropriate in some more specialist circumstances.

1. The values used
here are ones that the Numerical Recipes authors suggest "may
be slightly superior" to other recommended values (3rd ed, p. 346).

2. L'Ecuyer, P. & Simard, R. (2007) *TestU01: A C Library for Empirical Testing of Random Number Generators*, ACM Transactions in Mathematical Software **33**

3. In fact, they generally also use *substitution*: taking some partial value and
using it as an index into an array of "random-looking" values in order to add additional unpredictability.

Editorial page content written by Neil Coffey. Copyright © Javamex UK 2021. All rights reserved.