Skip to main content

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.

XYX XOR Y
000
011
101
110

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.
          
24 23 22 21 20
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!







Labels:

Comments

Post a Comment

Popular posts from this blog

VLC skins

It's been a while from my first blog post, so today I thought to make a blog post about skins in VLC player. I think you all are familiar with VLC player if not, here's the link for the website www.videolan.org/vlc/index.htm l In brief, VLC player is a free and opensource player that can play almost all the types of media formats. Even though it is a such a nice player, it looks kind of old and rusty, like the windows classic look. But you can make it prettier by just adding some new skins to it.  You can download skins for the player from here http://www.videolan.org/vlc/skins.php Then place the downloaded skin file (.vlt file) in the " skin " folder in the installation directory.           eg:- in windows:    C:\Program Files\VideoLAN\VLC\skins           or in linux systems:  ~/.local/share/vlc/skins Then, open the VLC player and go to the preferences. ...
2 comments
Read more

Java, how to create a list with a single element

 I wanted to create a Java List with a single element. Yet, I wanted to add more elements later. So, I was looking for a couple of ways to do this. So far there are multiple elegant ways to create a list with a single element with a one-liner. Not so much for a modifiable list though. Here's what I gathered so far. Followings are a few ways of creating a list with strictly a single entry. Can't add more elements. 1. Collections.singletonList() This returns an immutable list that cannot be modified or add more elements. // An immutable list containing only the specified object. List<String> oneEntryList = Collections. singletonList ( "one" ) ; oneEntryList.add( "two" ) ; // throws UnsupportedOperationException 2.  Arrays.asList() This returns a fixed-size list consisting of the number of elements provided as arguments. The number of elements provided would be an array hence the size is fixed to the length of the array. // Returns a fixed-size list List...
Post a Comment
Read more

Find command: How to find and delete 0 bytes files in Linux

In Linux, "find" command is a powerful command that we can use not only to find files. I've used it for different requirements, so thought of posting some of the convenient usages of find commands in a series of posts. For some application issue, I've got one of my directories in Ubuntu system swarmed with empty files with 0 bytes. Some of the files got data in them but some of them were empty. I just wanted to delete the empty files and it wasn't possible to identify them by file names or dates. So find command comes to rescue. find . -size 0 -type f  If I needed to isolate the files by file extension, we can use something like this. find . -size 0 -type f -name "*.tar" You can get the file count by piping it to wc command. find . -size 0 -type f -name "*.tar" | wc -l The awesome thing about the find command is you can use it for deleting files just by adding the -delete flag to the command. find . -size 0 -type f -name "*.tar" -dele...
Post a Comment
Read more