Programming tricks of the day.

XOR

XOR (exclusive OR) is one main basic logic operations on all computers. Its a binary operator that takes two bit patterns and combines them (hopefully) is a useful manner. Often times XOR is represented by the carrot character, ^

Sample XOR operations:

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

As you can see from the table, the output of an XOR operation is "0" if both bits are the same, and the output is a "1" if only one if the bits is a "1". If the two oeprands have multiple bits, then each corresponding bits in the two numbers is XOR'ed seperately.

This would just merely seem like logic designer's having too much time on their hands (and in many cases do) however the XOR operation is very usefully in certain situations.

Uses in encryption:

The XOR operation is self repeating. Say you have the number A = 0101 and you wanted to send it secretly. One way to do so if using XOR encryption, the involves picking a key. A key, in this case, is just a sequence of bits the same length as the message you want to encrypt, call this number K.

The encrypted message, E, is A ^ K

To decrypt the message E, XOR it with K again E ^ K = A

As you can see, XORing twice with the same number gives you back what you started. FOr an example let's encrypt our number, A = 0101 with the key, K = 1110

A = 0101
K = 1110 ^
-------------
E = 1011

Send E out to the other person, the other person, knowing E and the secret key, K, simply XORs them together to find the original message.

E = 1011
K = 1110 ^
-------------
A = 0101

Obviously, encrypting 4 bits doesn't serve much practical good, but this method can extend to any number of bits and encrypt any length message. In fact, this basic method is the base behind DES encryption, which in itself the base behind modern RSA encryption techniques.

Quick memory clearing:

A not so obvious result of an XOR is what happens when a number is XORed with itself. A simple test will figure that out

1011
1011 ^
---------
0000

An intersting result. Any number XORed with itself will give all zeros. Besides being useful, this method is extremely fast. Modern processors can perform XORs with upwards of 32 to 64 bits in less than a single clock cycle. This simple fact is the basis behind the fast clearing of memory including most retail hard drive wiping software.

Programming Trick:

If you've taken a programming class, then you've almost certainly had to write a swap function. A function that takes two parameters and returns the two with their values switched. The following is a common C++ implementation.

void swap(int& a, int& b)
{
int temp = a;
a = b;
b = temp;
}

The above works, but at the expense of a temporary variable. You might think it impossible to do the above swap operation without that temporary variable. I'd be willing to guess most programming teachers would agree. However, believe or not there is a way to perform the swap function without a temporary variable. And you do that with the XOR.

void swap(int& a, int& b)
{
a = a ^ b;
b = b ^ a;
a = a ^ b;
}

Don't believe me? Try it.

Later.

very interesting entry!
An aside: you can also swap values using multiplication & division, but yea, that'd be very inefficient.
» dave on 2005-08-02 11:59:33

I STRIKE YET AGAIN!!! YOU CANNOT ESCAPE ME!!!
» Crustache Mcgoocherson (216.230.10.131) on 2005-08-03 03:13:22

Excuse, I have removed this phrase
Yes, really. I join told all above. adipex online It agree, very much the helpful information Lorazepam online You have thought up such matchless phrase? valium pharmacy It does not disturb me. buy meridia online You not the expert? get codeine c7fd1d
» Lane (60.21.136.22) on 2010-09-01 10:46:59

Name.

URL.

[to enter your email, use "mailto:[email protected]"]
Subject.

Comment.

Word verification.

Copy the first 4 characters only.

If you are a member, try logging in again or accessing this page here.