The Magical Exclusive OR (XOR)

• Download source - 29.63 KB

Introduction

XOR is a logical operation between binary number 0 or 1, it can help us solve problems in simple way sometimes. In this article, I’ll show you what XOR can do, and how to implement it.

Background of XOR

What is a XOR? When you XOR two numbers, the rule of result is:

0 XOR 1, the result is 1, 1 XOR 0, the result is 1; 0 XOR 0, the result is 0, 1 XOR 1, the result is 0. You can instead 0 and 1 of False and True. It means when the operands are the same, the result is 0 (or False), otherwise is 1 (or True). In another words, XOR can show you if are there some differences between operands. By its function, what can we use it to do?

3 Functions in XOR

1. Switch Values of Two Variables

Question

Assume that there are two variables that look like the following: A = 3, B = 5. Now, you need to switch the value of them, after switch, they look like: A = 5, B = 3.

Answers

There are 3 ways to switch them:

Method 1. Define a new variable C, Save the value of A to C, and save the value of B to A, finally, save the value of C to B, see the following pseudo code:

int C = A; // define a new variable C, it saved the value of A
A = B;     // Save the value of B to A    
B = C;     // Save the value of C(come from A in first line) to B     

Then, the values of A & B were switched.

Method 2. The another way is use the mathematical method, the principle is let one variable(assume A) save the discrepancy of them, another variable(B) add the discrepancy, then it will become A, and the result of variable B subtract the discrepancy is A, pseudo code is:

A = A – B; // let a save the discrepancy of A & B
B = A + B; // the discrepancy(new save in A) add B, save in B; now B is the 
	  // value of A what before changed
A = B – A; // B subtract the discrepancy save in A, now A is the value of B 
	  // what before changed

You can verify this method following the above code; the values of A & B were switched.

Method 3. Switch them by XOR operation. This way is similar with way 2. See the following:

A = A ^ B; // Save the XOR operation result of A & B to variable A
B = A ^ B; // Save the XOR operation result of A (result of A & B at last step) & 
	  // B to variable B
A = A ^ B; // Save the XOR operation result of A (result of A & B at first step) & 
	  // B (result of A & B at last step)

(The symbol ^ is XOR operation in C#, you can change to the right symbol in the language that you are writing).

You can see these codes are so cool, the operation and operands are the same in the right side each line, after 3 operations, the values were switched.

2. Back up Information

How does a XOR operation backup data? As we know, for backing up data, we can save a copy of data before it gets a modification, and then recover it after modification, if we need. But if there are a hunt number of data needed to be backed up, saving a copy for each data is so expensive for room (memory or disk space). Using XOR operation, we can only use one data for recovering all data. First of all, we must know another feature of XOR, see the following.

Assume there are 3 variables, A, B & C, we get the fourth variable X, then let X as A^B^C. this means, variable X is the result of A XOR B, and XOR C. Now you can have a try, these 4 variables have the following relation:

X = A^B^C;  // Save the result of A, B & C to variable X

Then:

A = B^C^X; // the value of A is the XOR operation result of B, C & X
B = A^C^X; // the same as above, instead of B
C = B^C^X; // the same as above, instead of C

In other words, if the variable X is the result of A, B & C, one of these 4 variables is the XOR result of the other 3 variables.

Then we get such an interesting feature, how does it back up data?

As the above pseudo code assumes there are 3 files (file1, file2 and file3) saved in disk, and we need a back up, once one of these 3 files crashed, it could be recovered. So, we create another file (FileX), while file1 crashed, we can rebuild it by the following operation: file1 = file1 ^ file2 ^ FileX. You can see the sample code for implementation. You can see that each file is read as binary array, and takes XOR operation. The benefit of the method for backing up data is only wave a little size data, and can back up a lot of data, but the weakness is that it needs a large number of operations.

3. The Third Function of XOR is Encryption

A very sample encryption in some cases can use XOR. When a message needs to be encrypted, let it XOR with a fixed message, the result is the cryptograph, while we need to get the origination message, the cryptograph XOR with fixed message, the result is origination message. You can try it yourself.

Code Description

The attached code shows you how XOR operation backs up 3 files with only one file. There are 3 text files in Debug folder, while you click button <Back up>, a new text file FileX.txt will be created, it contains the XOR result of existing 3 files, it is the backup data of the above 3 text files. And then, you delete <file2.txt>, and click <Recover>, the file2.txt comes back! Try it, and contact me at kentbill@gmail.com if you have any questions.

History

• 17^th August, 2011: Initial version