Apply XOR operator for integers

I am writing this post to answer a question from a student who studies IT at school. 

They had this MCQ question where this Python code of XORing two integers several times and finding the output. 

Question

a = 20

b = 30

a = a ^ b

b = a ^ b

a = a ^ b

The question is to find the output results of a and b. If I type this code in the Python interpreter, I get the below outputs.

XOR of two numbers - Hard way

First I'll explain how to do this properly for the sake of completion. If you know this already, you can just skip this and follow the easy answer.

First of all, it was not a computer-based exam, you have to think this through in your mind using pen and paper. 

Second of all, how on earth do you apply XOR into integers? It's been a while I learned boolean algebra and I'm pretty sure boolean means true or false. 

Then it kicked me, boolean also means 1s and 0s, where you can represent integers using 1s and 0s or binary and then apply the XOR. In fact, that's how actually the Python compiler does it. Let's try to XOR two integers, 20 and 30.

20 in base 10 can be converted to binary. You can convert a number into binary by keep dividing a number by 2 and deriving the remainders.

      remainders

2|20 -> 0

2|10 -> 0

2| 5 -> 1

2| 2 -> 0

   1 -> 1

So, the binary of 20 is 10100. 

Now, let us consider 30 and convert it into binary.

      remainders

2|30 -> 0

2|15 -> 1

2| 7 -> 1

2| 3 -> 1

   1 -> 1

So, the binary of 30 is 11110.

Now, you have two binary numbers and all you have to do is to apply the XOR operation. The truth table of the XOR is below.

X	Y	X XOR Y
0	0	0
0	1	1
1	0	1
1	1	0

If we apply this to the above two numbers;

    10100

XOR 11110

    01010

Now, we need to find the decimal value of this number. Here's how you do that.

A binary number can be represented as placements of powers of 2.

          

2⁴ 2³ 2² 2¹ 2⁰

^{0  1  0  1  0 -->   8 + 2 = 10}

---

XOR of two numbers - Easy way

While converting back and forth binary to decimal above, you may have noticed, binary is always about representing a number with powers of 2. 

Let's try to do that without converting it into 1s and 0s.

Let us consider 20

First, find out the largest power of 2 closer to 20. It is 16. Let's write it down.

16

Then, in order to make 20, how much we need? It's 4. And what's the largest power of 2 closer to 4. 4 itself is a power of 2. Let's write it down also.

16, 4

If we add them together, we get 20. So, 20 can be represented by 16 + 4.

Similarly, Let's consider 30.

What's the largest power of 2 closer to 30? It is again 16. Let's write it down.

16. 

Taking out 16 from 30, what's left is 15 (30-16=15).

What's the largest power of 2 closer to 15? It is 8. Let's write 8 also along with 16.

16 + 8

Again what is left from 30 is 30 if we take out 16 and 8. 30 - 16 - 8 is 6. What's the largest power of 2 closer to 6? It is 4. Let's write it down along the same.

16 + 8 + 4

Again 30 - 16 - 8 - 4 is 2. What's the largest power of 2 closer to 3? it is 2

16 + 8 + 4 + 2

Like we did earlier, if you add them together it becomes 30.

Let's try to do the XOR operation.

Now, I'm writing the powers of 2 which made above two numbers side by side.

16 + 4         XOR           16 + 8 + 4 + 2

Now, we have to literally do the XOR again. Simply what we have to do avoid duplicates and take out the non-duplicates. I'll just cross out the duplicate powers of 2 from each side.

16 + 4         XOR           16 + 8 +  4 + 2

Let's add what is left over.

8 + 2 = 10

It may be confusing at first, but practice it a couple of times, you'll get the hang of it.

Now, let's try to solve the above problem with this technique.

Solving the question

first, a = 20 and b = 30

a = a^b     ->     16 + 4    XOR     16 + 8 + 4 + 2     -> 10

now, a = 10 and b = 30

b = a^b     ->     8 + 2     XOR     16 + 8 + 4 + 2     -> 20

now, a = 10 and b = 20

a = a^b     ->     8 + 2     XOR     16 + 4             -> 30

You may notice that there is nothing common to cut off. So we add them all together.

If you are working on an MCQ question, this would help you to save a couple of minutes!

The trick of the question

If you check the question, what it gives two values and apply XOR over and over three times. Surprisingly the outcome is the values have been swapped. 

The trick of this question is it is true for any couple of values, if you XOR it 3 times, the original values are being swapped. 

Just to be sure, let's get some random two numbers and see if it is true. I'm using the Python interpreter because I'm too lazy to write it down and do it manually.

One more thing

You should always remember, XOR of the same number is always 0. So you don't even have to do the above calculation.

eg: 

10 XOR 10 = 0

With our method;

8 + 2 XOR 8 + 2

8 + 2 XOR 8 + 2  = 0   (both sides are similar, so I can cut them off)

Just to be sure let's run this in Python

That's all folks! Try out if the above little trick can be applied to other boolean operations also!