Logic behind bitwise operators in C

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.

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.

i

j

i

j

3 Answers
3

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
$$beginalign
d &= b oplus c\
&= b oplus (a oplus b)\
&= b oplus (b oplus a)\
&= (b oplus b) oplus a\
&= a.\
endalign$$

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

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 $-1equiv 1$ and $-0equiv 0 pmod 2$. So what is left in the bitwise version is exactly

UINT_MAX+1

i ^= j; j ^= i; i ^= j;


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

Thanks for contributing an answer to Mathematics Stack Exchange!

But avoid …

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.