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.