Prove that the mapping of a number to its XOR with some constant c is bijective

Question

Prove that $x \mapsto x \oplus c$ is a bijection over the range $[0, b]$, regardless of the value of constant $c$, where $b = 2^{k} - 1, k \in I^{+}$.

Answer 1

The range $[0,b]$ is just all bit-vectors of a given length, here, $k$.

First, you should prove that, for any bit-vectors $x, y,$ and $z$, $$ x \oplus (y \oplus z) = (x \oplus y) \oplus z, $$ that is $\oplus$ is associative. To show this, you can look at each of the indices of the bit-vector separately.

From this, you can then show: $$ (x \oplus c) \oplus c = x \oplus (c \oplus c) = x \oplus 0 = x. $$ That means the map which sends $x$ to $x \oplus c$ is invertible -- the operation $x \oplus c$ can be "undone" by doing $\oplus c$ again. So the map must send each input to a unique output. That is, it's injective.

Finally, the input set (all bit-vectors of length $k$) and the output set (all bit-vectors of length $k$) are the same. So since the map is injective, it must also be surjective.