Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Let's say we have given two numbers $x, z$, and we need to find another number $y$ such that $x \text{ xor } y = z$. The xor ( exclusive or ) is bitwise operation: xor table .
I know that this can be solved if we analyze both $x \text{ and } y$ bit by bit, starting from the first, but I was wondering if it can be solved by some easier way with bitwise operations.
One can observe that, for any boolean values $a,b,c$, we have $a=b$ if and only if $a \text{ xor } c = b \text{ xor } c$.
(To prove that we note that $\Rightarrow$ is trivial, and $\Leftarrow$ follows by xor-ing with $c$ once more and applying the cancellation law.)
Hence, the equation $x \text{ xor } y = z$ is equivalent to $(x \text{ xor } y) \text{ xor } x = z \text{ xor } x$ which in turn (by the cancellation law), simplifies to $y = z \text{ xor } x$.
If we wanted to be more pedantic we could explicitly point out those steps where we also implicitly used associativity, commutativity, and the identity law.
Xoring is "reversible": $y$ xored by $x$ flips the bits of $y$ where $x$ has ones. Xoring one more time restores the initial value.
$$(y\oplus x)\oplus x=y=z\oplus x.$$
