0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hint: $x \text{ xor } (x \text{ xor } y )= y$ $\endgroup$ – Yves Daoust Jul 17 '18 at 8:31
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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