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
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.
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; A = B; B = C;
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; B = A + B; A = B – A;
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; B = A ^ B; A = A ^ B;
(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;
A = B^C^X; B = A^C^X; C = B^C^X;
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.
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 firstname.lastname@example.org if you have any questions.
- 17th August, 2011: Initial version