2
$\begingroup$

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)$.

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.