Click here to Skip to main content
Click here to Skip to main content

The Magical Exclusive OR (XOR)

, 17 Aug 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
XOR operation is magical and what can it do for you? It can switch the values of variable, back up and encrypt data.

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

  • 17th August, 2011: Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

KentBill
Program Manager LEO Paper Group
China China
I'm a developer and now I managing a project in my company -LEO paper group of HongKong, China. I hope learn more knowledge in this project, I'll share what I get in it while the proejct complete. I'm living mainland China. send me a e-mail at kentbill@gmail.com for more communications.
Follow on   Twitter

Comments and Discussions

 
Question[My vote of 2] flaws Pinmembermounte@cognimatics17-Aug-11 12:30 
AnswerRe: [My vote of 2] flaws PinmemberKentBill10-Nov-11 5:59 
the answers of your questions are below.
1. Why you need to switch them if A == B ?
2. It can switch numeric values, as char or a string (a array of char), you can switch their ASCII code.
I'm coding everyday and enjoy it.

SuggestionWhy duid you not just edit + the table??? PinmentorDaveAuld17-Aug-11 9:41 
Question[My vote of 1] Nothing significant here Pinmemberpt140117-Aug-11 9:34 
AnswerRe: [My vote of 1] Nothing significant here PinmemberKentBill18-Aug-11 0:37 
AnswerRe: [My vote of 1] Nothing significant here PinmemberXiaoChuan Yu18-Aug-11 4:57 
GeneralRe: [My vote of 1] Nothing significant here PinmemberMember 434443422-Aug-11 14:41 
GeneralRe: [My vote of 1] Nothing significant here PinmemberPete Goodsall23-Aug-11 4:47 
QuestionOne correction PinmemberB1g0n317-Aug-11 8:33 
AnswerRe: One correction PinmemberKentBill18-Aug-11 0:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.141223.1 | Last Updated 17 Aug 2011
Article Copyright 2011 by KentBill
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid