Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$

Question

Let $\mathbb{Z}_2^n$ be the field of bitvectors of length $n$ and define the xor operator $\oplus$ and the addition operator $+$ over this field, with $+$ having the usual overflow semantics (take addition modulo $2^n$).

Is it possible to express any mapping $f: \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2^n$ entirely in terms of $\oplus$ and $+$? It seems like it might be possible due to the nonlinearity of $+$.

---

For instance, if we were given $n=2$ and that $f(0) = 3, f(1) = 1, f(2) = 3, f(3) = 1$, then we could construct $f$ as $f(x) = x\oplus(x+3)$.

Answer 1

Nope. For instance, you can't express the function $f(x)=x>>1$. In general, the least-significant bit of $f(x)$ depends only on the least-significant bit of $x$. You can prove that by structural induction, using the following two properties: $(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$ and $(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \bmod 2$.