Stronger, better, morer, Moremur; a better Murmur3-type mixer.

I'll keep this brief: The original constants used in MurmurHash3 and Stafford's Variant 13 are not as good as they could have been. This affects the strength of SplitMix64.

The testing procedure I've used is described in an earlier post. There is one extension, compared to the earlier post: every rotation and reversal is also complemented for a total of 256 subtests. I'll call the extended version "RRC-64-40-TF2-0.94" for "Reversed, rotated, complemented-64 bits, 2^40 bytes, PractRand 0.94 with -tf 2". Without further ado, here's "Moremur", a statistically stronger but equally fast mixer:

uint64_t moremur(uint64_t x) {
  x ^= x >> 27;
  x *= 0x3C79AC492BA7B653UL;
  x ^= x >> 33;
  x *= 0x1C69B3F74AC4AE35UL;
  x ^= x >> 27;

  return x;
}

One strong flaw with this construction, i.e. the first operation being an xor-shift, is that there are many increments that will lead to few or none of the less significant bits being one. This in turn implies that the less significant bits will be zero after the first two operations, xor-shift and multiply. Particularly bad increments have this form: $\gamma = (2^s + 1)a, a \lt 2^s$, $s$ being the first shift and $a$ being sparse.

In the table below, Moremur outperforms Murmur3 and Variant13 by quite some margin.

Table 1: Test length where PractRand fails

$\gamma$	Murmur3	Variant13	Moremur
0x0000000000000001	$2^{17}$	$2^{19}$	$2^{33}$
0x0000000000000003	$2^{17}$	$2^{17}$	$2^{34}$
0x0000000000000005	$2^{17}$	$2^{18}$	$2^{34}$
0x0000000000000009	$2^{16}$	$2^{18}$	$2^{34}$
0x0000010000000001	$2^{18}$	$2^{21}$	$2^{41}$
0xffffffffffffffff	$2^{17}$	$2^{19}$	$2^{33}$
0x0000000000ffffff	$2^{17}$	$2^{23}$	$2^{37}$
0xffffff0000000001	$2^{18}$	$2^{23}$	$2^{43}$
0x0000000000555555	$2^{18}$	$2^{28}$	$2^{42}$
0x1111111111110001	$2^{25}$	$2^{30}$	$> 2^{46}$
0x7777777777770001	$2^{28}$	$2^{34}$	$> 2^{45}$
0x7f7f7f7f33333333	$2^{30}$	$2^{33}$	$> 2^{46}$
0x5555550000000001	$2^{21}$	$2^{27}$	$2^{45}$
0xc45a11730cc8ffe3	$2^{39}$	$> 2^{42}$	$2^{?}$
0x2b13b77d0b289bbd	$2^{39}$	$> 2^{42}$	$2^{?}$
0x40ead42ca1cd0131	$2^{40}$	$> 2^{42}$	$2^{?}$

As can be seen from the tables below, these constants are a great improvement over the ones I've been aware of so far (original MurmurHash3 and Variant13). Moremur still fails RRC-64-40-TF2-0.94 but far from as badly as the earlier constants do.

Moremur failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	27	28	29	16	16	16	17		16	17	19	19	20	28	27	28	34	29	29	35	36	37	37	38
16	17	17	18	19	19	19	19	20	21	22	23	23	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	31	31	32	33	33	34	34	34	34	34	33	32	32		28	34	33	32	32	31	33	33	34	34	34	35	35	36	37	36
48	32	28	28	28	29	29	29	29	30	30	30	30	31	31	31	32		31	31	31	33	36	37	36	28	33	34	31	31	28	25	22	19
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	19	19	19	22	22	24	25	28	29	18	28	15	16	16	17		16	17	19	21	21	26	28	30	34	31	34	34	36	36	37	37
16	17	18	18	19	19	19	19	19	21	22	23	24	24	25	26	27		36	35	35	39	40	34	31	31	39	40	39	38	37	34	34	36
32	28	29	30	30	32	33	33	34	34	35	35	34	34	32	33	32		28	34	33	32	32	31	33	33	34	34	34	35	36	36	36	36
48	32	28	28	28	28	28	29	29	29	30	30	30	31	31	32	32		31	31	31	33	35	35	34	28	32	32	31	30	28	25	22	19

Murmur3 failures, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	18	18	18	17	16	16	16	16	15	15	17	15	14	15	15		15	17	18	18	18	17	17	16	16	14	14	14	14	14	14	17
16	14	14	14	14	14	15	15	15	15	15	16	16	16	16	15	15		17	17	16	17	17	17	17	18	19	17	18	18	17	16	14	14
32	16	16	17	17	16	16	14	14	16	15	14	15	15	15	15	15		15	16	17	18	18	17	17	17	17	16	14	14	14	14	15	15
48	15	14	14	14	14	14	15	15	15	15	15	16	17	17	17	17		17	17	17	17	17	17	17	18	18	19	19	18	18	18	17	16
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	17	18	17	17	15	16	16	16	15	15	17	14	15	15	15		14	17	18	18	17	17	16	17	16	15	14	14	14	14	16	17
16	14	14	14	14	15	15	15	15	15	15	16	16	16	16	15	15		17	17	16	17	17	17	17	18	18	18	17	16	15	15	14	14
32	16	17	17	17	16	14	14	14	15	15	14	15	14	15	15	14		15	15	17	18	18	17	17	17	17	16	15	14	14	14	14	15
48	14	14	14	14	14	14	15	15	15	15	15	16	17	17	17	17		17	17	17	16	17	17	17	17	18	19	19	18	18	18	17	15

Variant 13, $2^{40}$ bytes maximum.

ror64(reverse(x, R) ^ 0x0000000000000000, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	19	17	18	18	18	17	18	18	18	18	18	19	19	16	17	17		16	17	18	18	18	19	19	20	20	19	20	20	19	20	20	19
16	17	17	16	17	16	16	17	17	16	17	16	17	17	17	18	18		20	19	21	18	19	21	19	22	20	21	22	21	20	22	22	19
32	19	19	19	19	19	19	19	19	19	19	20	20	19	20	19	19		18	18	18	19	19	20	20	19	20	20	19	20	20	20	20	19
48	17	17	16	17	17	17	16	17	16	17	17	17	18	18	19	19		21	18	18	21	19	22	20	21	19	18	18	18	18	18	18	18
ror64(reverse(x, R) ^ 0xFFFFFFFFFFFFFFFF, r)
	FORWARD																	REVERSED
Offset	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15		0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	19	17	18	18	18	17	18	18	18	18	18	18	19	16	17	17		16	17	18	18	18	19	19	20	20	19	20	20	19	20	20	19
16	17	17	16	17	16	17	17	17	16	17	16	17	17	17	17	18		20	19	21	18	18	21	19	22	20	21	22	21	20	22	22	19
32	19	19	19	19	19	19	19	19	19	19	20	20	19	20	20	19		18	18	18	19	19	20	20	19	20	20	19	20	20	19	20	19
48	16	17	16	16	17	17	16	17	16	17	17	17	18	18	19	19		21	19	19	21	19	22	20	21	19	18	18	18	18	18	18	18

The constants were found through a stochastic hill climber I wrote using CUDA. The first testing I did of Murmur3 and Variant13 revealed that they had fairly weak higher order avalanche properties. Letting the fitness function include metrics for 1st to 4th order avalanche proved to be quite successful. The CUDA program was used for sieving; once some possibly good candidates turned up, I ran them through RRC-64-40-TF2-0.94. The constants above were the best I could find; the fitness function, combining several tests, was too insensitive to make any further improvements possible with the approach I used.

Conclusion

The shifts and constants above give a permutation that is statistically closer to a pseudo-random permutation than the ones used in SplitMix64, java.util.SplittableRandom and java.util.ThreadLocalRandom. In particular, the number of bad gammas/increments should be considerably fewer.

Better, stronger mixer and a test procedure.

An intermediate result (much stronger mixer).

A frustrating search.

When working on finding good mixers, I got really frustrated by the extremely slow process of testing a new set of constants or other tweaks to functions that were "kind of good".
My criterion for "success" was that the output from a simple counter, starting at 0, passed to the mixing function, and then taking the output from the mixing function and feeding it to PractRand with -tf 2 should not generate any failures up to $2^{45}$ bytes.

Eventually, I came to realize that what I really wanted was not just a function that would satisfy the "generate PractRand-passing output when fed a unitary counter" but rather "a decent approximation of a random permutation". Such a permutation would give a higgledy-piggledy sequence from a very regular one, regardless of what the regularity looks like (just kidding; the regularities of interest are affine transformations, of course there are many other sequences one could think of as "regular"). Previosuly, I had been testing with feeding gray-code sequences to the mixing function, hoping that the unit Hamming distance between adjacent inputs would reveal flaws more quickly. For the functions I tested, I couldn't find that it made any difference w.r.t. how quickly testing failed.

As I was thinking about more sequences that would be "very well ordered" I came up with a very simple testing procedure that seems to work well: A function that pass the subtests described below is also very likely to work well on any kind of (affine) counter update.

The fact that many of the subtest input sequences intersect does not affect the tests since they are run independently.

Test procedure

Instead of testing the full output, which is very slow, test many short output sequences in the hopes that anomalies in the mixer will be revealed more quickly. There's quite some conjecturing here: the (lack of) failures on many short tests hopefully correlate with overall quality. If the mixer is good, this is also a very lengthy process (the way I have been doing it, 128 TB of data will be tested if there are no failures) but running many small tests (1 TB a piece) can be done in parallell on a machine with many cores but without a using a lot of RAM.

Naming

To avoid confusion, let's call this test procedure "RR-b-x-TF2-0.94". "RR" to indicate "rotate and bit reversal", "b" for the word size in input/output bits, x for the tlmax-exponent, TF2 to indicate that PractRand was run with "-tf 2" and "0.94" for the version of PractRand I am currently using. The same procedure can be used for any permutation of size $2^{8b}$. Pseudo-code for RR-b-x-TF2-0.94:

# The tests I have run have been with b = 64 and x = tlmax = 40,
# i.e. 1 TB per subtest.
# rfun is either the identity function or a b-bit bit-order reversal function.
for rfun in {identity, bitreversal}
  # Rotate counter 0 to (b - 1) bits.
  for r in {0, ..., b - 1}
    # No failure seen for this rfun & rotation so far.
    failure = 0
    # 2^x bytes, 2^x / b * 8 b-bit words.
    for ctr in {0, ..., (2^tlmax / b * 8) - 1}
      # Feed PractRand, break on failure.
      # RORb is a b-bit right rotate function.
      if feedPractRandFails(RORb(rfun(ctr), r))
        # Note the failure level.
        failure = ceil(log_2(ctr))
        break for
      end if
    end for
    emitTestScore(rfun, r, failure)
  end for
end for

Test results

MurmurHash3 finalizer

RR-64-40-TF2-0.94 fails the MurmurHash3 finalizer quickly. This is to be expected considering that it is known to fail quickly when fed a unitary counter.

MurmurHash3 failures, $2^{40}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	17	18	18	18	17	16	16	16	16	15	15	17	15	14	15	15
16	14	14	14	14	14	15	15	15	15	15	16	16	16	16	15	15
32	16	16	17	17	16	16	14	14	16	15	14	15	15	15	15	15
48	15	14	14	14	14	14	15	15	15	15	15	16	17	17	17	17
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	17	18	18	18	17	17	16	16	14	14	14	14	14	14	17
16	17	17	16	17	17	17	17	18	19	17	18	18	17	16	14	14
32	15	16	17	18	18	17	17	17	17	16	14	14	14	14	15	15
48	17	17	17	17	17	17	17	18	18	19	19	18	18	18	17	16

MurmurHash3, Variant 13

RR-64-40-TF2-0.94 fails Variant 13 quickly too. This is also to be expected considering that it is known to fail almost as fast as the MurmurHash3 finalizer.

MurmurHash3/Variant 13 failures, $2^{40}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	19	17	18	18	18	17	18	18	18	18	18	19	19	16	17	17
16	17	17	16	17	16	16	17	17	16	17	16	17	17	17	18	18
32	19	19	19	19	19	19	19	19	19	19	20	20	19	20	19	19
48	17	17	16	17	17	17	16	17	16	17	17	17	18	18	19	19
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	16	17	18	18	18	19	19	20	20	19	20	20	19	20	20	19
16	20	19	21	18	19	21	19	22	20	21	22	21	20	22	22	19
32	18	18	18	19	19	20	20	19	20	20	19	20	20	20	20	19
48	21	18	18	21	19	22	20	21	19	18	18	18	18	18	18	18

Ettinger's mixer

Tommy Ettinger came up with a quite different construction, compared to MurmurHash3 (and variants) and my own rrmxmx (in C):

uint64_t ettingerMixer(uint64_t v) {
  uint64_t z = (v ^ 0xDB4F0B9175AE2165UL) * 0x4823A80B2006E21BUL;
  z ^= rol64(z, 52) ^ rol64(z, 21) ^ 0x9E3779B97F4A7C15UL;
  z *= 0x81383173UL;
  return z ^ z >> 28;
}

According to him it passes 32 TB of PractRand but with -tf unspecificed, defaulting to 1 instead of 2 which is what I use for all tests. I was a bit too quick here and tested his function with RIGHT-rotates and not LEFT-rotates which is what Ettinger used. The table below is now updated to reflect a correct implementation of his mixer. The performace w.r.t. RR-64-40-TF2-0.94, compared to my incorrect implementation, is about the same. 122 failed tests out of 128:

"Ettinger's mixer" failures, $2^{40}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	40	16	16	15	14	15	16	16	15	12	12	13	14	15	14	15
16	15	16	15	16	16	17	18	19	17	17	17	17	18	17	17	18
32	19	20	21	23	24	25	26	27	28	28	30	30	32	24	19	16
48	16	19	19	19	22	22	24	31	40	40	40	40	36	34	40	40
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	13	15	14	15	15	15	15	16	16	16	16	16	16	16	17
16	17	18	19	19	22	20	20	17	23	25	25	25	26	30	30	29
32	30	34	33	36	21	19	17	16	17	16	16	17	21	21	19	19
48	22	22	21	20	21	20	19	20	19	18	16	16	16	15	15	14

So this is a special case where an increment of one works particularly well. It would be interesting to know at what level it fails PractRand (with -tf 2, if at all) with a unitary counter.

Changing the rotation constants to {12, 43} (corresponding to right rotates instead of left rotatets) gives a function with about the same number of failures, 120 out of 128:

"Ettinger's mixer, ROR-version", $2^{40}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	40	15	15	14	15	15	16	16	15	15	15	15	15	15	15	15
16	16	16	16	16	16	16	16	18	18	17	18	17	18	19	19	18
32	17	18	19	21	23	19	17	17	19	19	19	21	24	28	31	35
48	36	37	38	34	36	36	35	38	40	40	40	40	40	40	40	40
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	14	14	15	15	15	15	16	16	16	17	16	17	17	17	16
16	18	17	17	16	24	23	22	21	24	25	25	22	19	17	19	17
32	16	16	17	19	19	19	21	22	25	27	26	25	24	23	22	21
48	20	19	18	17	17	17	17	17	17	17	17	17	16	16	15	15

Testing rrmxmx

I already knew that rrmxmx fails PractRand -tf 2 -te 1 after $2^{44}$ bytes when fed a unitary counter, starting at 0. If I recall correctly that took about one week of computing time to find out. The table below took about 20 minutes to generate and it clearly shows that rrmxmx is far from optimal (note that x = 33, quick and dirty):

The original rrmxmx, $2^{33}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	33	33	33	33	33	33	33	33	25	25	33	33	33	33	33
16	33	28	33	33	33	33	33	33	33	33	33	33	33	33	33	33
32	33	31	33	33	33	33	30	30	30	33	33	33	33	33	33	33
48	33	33	33	33	33	33	33	33	33	33	33	33	33	33	33	33
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	33	33	33	33	33	33	33	33	33	33	31	28	31	33	33	33
16	33	33	33	33	33	33	33	33	33	33	33	28	33	33	33	33
32	28	28	30	25	22	33	33	33	33	33	33	33	33	33	33	33
48	33	33	33	33	33	33	33	33	33	33	33	33	33	33	33	33

The somewhat good news to anyone who decides to use it are that an increment of 1 is the only odd integer I have found which fails PractRand. The even better news is that a variation where the first ror-ror-xor and first shift-xor are interchanged in general performs better. For the constants I have tried so far, it still fails RR-64-x-TF2-0.94 but to a lesser extent. Which leads us to the latest and greatest. Even more rotates.

Intermediate result, my best so far

Compared to my previous function, rrmxmx, this is much more well behaved and has passed 128 TB of PractRand -tf 2 with a unitary counter (one single run, inputs $\{0, \ldots, 2^{44} - 1\}$). Testing with RR-64-40-TF2-0.94, there is 1 failure:

rrxmrrxmsx_0 failures, $2^{40}$ bytes maximum.

Offset	IDENTIY
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
16	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
32	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
48	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
Offset	REVERSE
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	40	40	40	40	40	40	40	40	40	40	40	40	40	40	39	40
16	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
32	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40
48	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40	40

Trying to fix this failure (ROR(reversed, 14)) has so far only given me variants with more failures or a single failure happening in a different subtest with less than $2^{39}$ bytes.

Compared to rrmxmx it is slightly slower, doing 2 rotations instead of the shift in the middle of rrmxmx. Temporarily, let's call it "rrxmrrxmsx_0" (in C):

// Old mixer, my rrmxmx
uint64_t rrmxmx(uint64_t v) {
  v ^= ror64(v, 49) ^ ror64(v, 24);
  v *= 0x9FB21C651E98DF25L;
  v ^= v >> 28;
  v *= 0x9FB21C651E98DF25L;
  return v ^ v >> 28;
}

// New mixer, "rrxmrrxmsx_0", failing one subtest of RR-64-40-TF2-0.94.
// With a unit counter starting at 0, it has passed 128 TB of
// PractRand 0.94 -tf 2 without anomalies found past 2 TB.
uint64_t rrxmrrxmsx_0(uint64_t v) {
  v ^= ror64(v, 25) ^ ror64(v, 50);
  v *= 0xA24BAED4963EE407UL;
  v ^= ror64(v, 24) ^ ror64(v, 49);
  v *= 9FB21C651E98DF25UL;
  return v ^ v >> 28;
}

I found this function a few months ago but have been hoping to find something of similar speed that doesn't fail any of the 128 subtests. If I do find one, I'll post it here!

I kind of gave up on finding better constants for functions having the same form as the original rrmxmx. To check that there really is a reasonable correlation between "quite good behaviour" when feeding the function with a unitary counter and not failing many subtests, I am running RR-64-40-TF2-0.94 on it. It fails much much less badly than MurmurHash3 and Variant13 but still much worse than rrxmrrxmxs.

Conclusion

Running RR-b-x-TF2-0.94 can be relatively quick way of detecting if a particular 64-bit permutation function is a good approximation of a random permutation. The approach can be extended to any permutation of size $2^{8b}$. As a preliminary step, one could lower x significantly. In case the function under test gives many failures at, say, x = 30, it may not be worthwhile to examine the number of failures at x = 40 or above. Passing the test is a necessary but not sufficient requirement for any function that is expected to behave like a random permutation. There are probably bad permutations that do pass RR-b-x-TF2 but no good ones that does not pass it.

Invertible additions, mod 2.

Invertible sums with shifted and/or rotated terms.

Under what conditions is this function bijective?

# 0 < r1 < r2 < w
f(x, w, r1, r2) {
  return x ^ ror(w, x, r1) ^ ror(w, x, r2);
}

Rotates, shifts and xors can all be expressed in terms of (binary) matrix addition and multiplication. So I simply wrote some code for Octave to construct the matrices corresponding to $f()$. Here's the relevant snippet in Octave/Matlab:

function retval = rotateMatrix(w, r)
  rs=eye(w); rs(:,1)=[];rs(:,w)=zeros(w,1);
  rr=rs; rr(1,w)=1;
  retval = mod(rr^r, 2);
endfunction

# Now f can be executed as a vector/matrix multiply with the following matrix:
rorrorxorMatrix = mod(eye(w)+rotateMatrix(w, r1)+rotateMatrix(w, r2), 2);

# If rorrorxorMatrix has an inverse, f is invertible.

If and only if the matrix is invertible for a $\{w, r_1, r_2\}$-triple, $w$ denoting the word length, will $f()$ be bijective on $2^w$.

Table 1: Invertible instances of x ^ ror(w, x, r1) ^ ror(w, x, r2) (f())

$w$	Distinct pairs	Invertible
3	1	No.
4	3	All
5	6	All
6	10	All but {1, 2}, {1, 5}, {2, 4}, {4, 5}.
7	15	All but {1, 3}, {1, 5}, {2, 3}, {2, 6},{4, 5}, {4, 6}.
8	21	All
9	28	All but {1, 2}, {1, 5}, {1, 8}, {2, 4}, {2, 7}, {3, 6}, {4, 5}, {4, 8}, {5, 7}, {7, 8}
10	36	All
11	45	All
12	55	All but {1, 2}, {1, 5}, {1, 8}, {1, 11}, {2, 4}, {2, 7}, {2, 10}, {4, 5}, {4, 8}, {4, 11}, {5, 7}, {5, 10}, {7, 8}, {7, 11}, {8, 10}, {10, 11}.
13	66	All
14	78	All but 24 pairs.
15	91	All but 37 pairs.
16	105	All
20	171	All
24	253	All but 64 pairs.
32	465	All
36	595	All but 160 pairs.
40	741	All
48	1081	All but 256 pairs.
56	1485	All but 384 pairs.
64	1953	All

2 shifts.

Somewhat similar are

# 0 < {r1, r2} < w, r1 < r2
f2(x, w, r1, r2) {
  return x ^ (x >> r1) ^ (x >> r2);
}

# 0 < l1 < l2 < w
f4(x, w, l1, l2) {
  return x ^ (x << l1) ^ (x << l2);
}

and

# 0 < {r, l} < w, but r may be equal to l.
f3(x, w, r, l) {
  return x ^ (x >> r) ^ (x << l);
}

$f_2()$ and $f_4()$ are bijective for all {r1, r2} or {l1, l2} as described above. ($f_4()$, with two left shifts, has the same properties w.r.t. inverses as $f_2()$.)
For $f_3()$, we're not so lucky. Only some pairs {r, l} give a bijection on $2^w$:

Table 2: Invertible instances of x ^ (x << l) ^ (x >> r) (f3())

$w$	Distinct pairs	Invertible pairs		$w$	Distinct pairs	Invertible pairs
3	4	1		14	169	108
4	9	5		15	196	135
5	16	4		16	225	165
6	25	14		20	361	266
7	36	18		24	529	422
8	49	33		32	961	769
9	64	34		36	1225	1007
10	81	46		40	1521	1223
11	100	55		48	2209	1880
12	121	88		56	3025	2510
13	144	73		64	3969	3330

3 & 4 shifts.

There are also many triples and quads on $2^w$ for $w = \{16, 32, 64\}$ (the most interesting $w$s if one wants to use these on a computer).

# 0 < {r1, r2, l} < w, r1 < r2
f5(x, w, r1, r2, l) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x << l);
}

# 0 < r1 < r2 < r3 < w
f6(x, w, r1, r2, r3) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3);
}

# 0 < r1 < r2 < w, 0 < l1 < l2 < w
f7(x, w, r1, r2, l1, l2) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x << l1) ^ (x << l2);
}

# 0 < {r1, r2, r3, l} < w, r1 < r2 < r3
f8(x, w, r1, r2, r3, l) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3) ^ (x << l);
}

# 0 < r1 < r2 < r3 < r4 < w
f9(x, w, r1, r2, r3, r4) {
  return x ^ (x >> r1) ^ (x >> r2) ^ (x >> r3) ^ (x >> r4);
}

Table 3: Invertible instances of $f_5, f_6, f_7$ & $f_8$

$w$	Distinct $f_5$, RRL/LLR	#Bijective $f_5$	Distinct $f_6$, RRR/LLL	Distinct $f_7$, RRLL/LLRR	#Bijective $f_7$	Distinct $f_8$, RRRL/LLLR	#Bijective $f_8$	Distinct $f_9$, RRRR/LLLL
16	1575	816	455	11025	5451	6825	3408	1365
32	14415	8226	4495	216225	109588	139345	73203	31465
64	123039	75429	39711	3814209	1958503	2501793	1271522	595665

Note that all instances of $f_6$ and $f_9$ are invertible, provided the constants are chosen with the constraints give above their definitions.

The tables can be found here.