9
$\begingroup$

I came across bitwise operations in C programming, and I realized that XOR operator can be used to swap 2 numbers in their binary bases. For example let $$i=(65)_{10}=(1000001)_{2}, \text{ and } j=(120)_{10}=(1111000)_{2}$$.

Let $\oplus$ be the XOR operator, then observe that if I started with any one of them, say $i$ and following the following procedure:

1)replace its value with the $\oplus$ value, yielding $$i=(0111001)_{2},j=(1111000)_{2}$$

2) replace the other variable($j$) with another $\oplus$ value derived from the new $i$ and old $j$, yielding $$i=(0111001)_{2},j=(1000001)_{2}$$

3)replace the original variable $i$ with $\oplus$ value again, yielding $$i=(1111000)_{2},j=(1000001)_{2}$$

which shows that we would somehow have their values swapped. I found this way of programming online and I definitely can’t understand how people think of the logic aspect of this. I would think it’s linked to the truth table as follows, which shows by division of cases that the values can be swapped.

enter image description here

However, I am still uncertain about the full reasoning why this works, like whether there is any mathematical theorems that I should know that can aid me in my understanding.

PS: Sorry if the question is off-topic here, it feels like a programming question, but I feel that I more concerned about the “logic” rather than the programming. I also drew the table myself on MS word since I can't get the latex one to work somehow.

$\endgroup$
  • $\begingroup$ Beware that this doesn't work if i and j happen to be the same variable! $\endgroup$ – Henning Makholm Sep 2 '18 at 13:59
  • $\begingroup$ @HenningMakholm ah ok noted, applying it 3 times has the same effect as applying 1 time and that will cause one of the values to be full of zeroes $\endgroup$ – Prashin Jeevaganth Sep 2 '18 at 14:03
  • 2
    $\begingroup$ It works for $i = j$ too. $\endgroup$ – mbjoe Sep 2 '18 at 14:11
  • $\begingroup$ @mbjoe oh ok just noticed $\endgroup$ – Prashin Jeevaganth Sep 2 '18 at 15:09
  • 9
    $\begingroup$ @mbjoe: It works for i and j having the same value, but not for them being the same variable. $\endgroup$ – celtschk Sep 2 '18 at 15:59
9
$\begingroup$

In algebraic terms, the XOR operator (or $\oplus$) is nothing other than addition modulo $2$: use $1$ and $0$ for true and false, along with $1 \oplus 1 = 0$.

Now, since addition modulo $2$ is associative and commutative, and both elements are their own inverses, we have $$\begin{align} d &= b \oplus c\\ &= b \oplus (a \oplus b)\\ &= b \oplus (b \oplus a)\\ &= (b \oplus b) \oplus a\\ &= a.\\ \end{align}$$

We can show $e = b$ using similar reasoning.

$\endgroup$
  • 1
    $\begingroup$ I prefer this to the accepted answer, since it mentions associativity and commutativity. Also, while obvious, I imagine the note that XOR is the same as addition modulo 2, might be helpful to readers. $\endgroup$ – Demosthenes Sep 3 '18 at 11:33
16
$\begingroup$

Note that you can do the same thing without bitwise operators (at least for unsigned integer types since they can't overflow into undefined behavior):

        // i == x     j == y
i += j; // i == x+y   j == y
j -= i; // i == x+y   j == -x
i += j; // i == y     j == -x
j = -j; // i == y     j == x

Now if we do this bit for bit, but modulo 2 instead of modulo UINT_MAX+1, the XOR operation implements both addition and subtraction, and the final negation is a no-op because $-1\equiv 1$ and $-0\equiv 0 \pmod 2$. So what is left in the bitwise version is exactly

i ^= j; j ^= i; i ^= j;
$\endgroup$
  • 1
    $\begingroup$ Thanks for the alternative solution to swap 2 numbers, this is insightful. $\endgroup$ – Prashin Jeevaganth Sep 2 '18 at 14:08
7
$\begingroup$

You already answered your question, but if you want an algebraic explanation note that for any $x$:

$$x \oplus 0 = x$$

$$x \oplus x = 0$$

So:

$$i_0 = i, j_0 = j$$

$$i_1 = i_0 \oplus j_0, j_1 = j_0$$

$$i_2 = i_1, j_2 = i_1 \oplus j_1 = i_0 \oplus j_0 \oplus j_0 = i_0$$

$$i_3 = i_2 \oplus j_2 = i_1 \oplus i_0 = i_0 \oplus j_0 \oplus i_0 = j_0, j_3 = j_2 = i_0$$

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