The Power of XOR

The Power of Xor

(No, this is not a science fiction story. Though maybe I'll write one called this someday...)

I decided to give a little example about the kind of math I am talking about when I say "discrete math". This example comes from the branch called "Boolean Algebra", named for George Boole, a 19th century English mathematician. All computer people ought to have a graph on their tee-shirts like this:



which, as I am sure you will recognize, is the equation for y = x(1-x). If you are a computer scientist and do NOT know this equation, shame. You had better take a good look at it - then maybe order Boole's book about it from Dover. (See sidebar for their address!)

OK, now - what is the XOR? All mothers know it, all children ignore it. After dinner, mothers ask, "do you want ice cream or cake?" and their children answer "Yes." (Some answer "Both" because they didn't read Mr. Boole's book yet!)

The mothers are using the English word "or" where they should be using the mathematical operation "XOR" - which we pronounce "ex-or". It's short for "exclusive or" - because the usual or is the "inclusive or" which is what the kids were using, because it includes the "both" case. (We could have called them "Mom's or" and "Kid's or", but some professor thought XOR up a while back, and the name stuck.)

The XOR function comes from Boolean Algebra, where the number-haters rejoice, because there are only two numbers: ZERO and ONE - and that's all! And the XOR function is a nice and very useful function, which can also be called the "not-the-same" function, for it gives an answer of ONE when you give it two DIFFERENT values, but ZERO when you give it the SAME values.

So, remember the multiplication table, that seemed to go on and on? All the tables in Boolean Algebra have only four entries, so let's set up the table for XOR. Here it is:


0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0


All done. Now, let's use it to do something very interesting.

Let's say we are holding an apple in our left hand, and an orange in our right hand. But we want it to be the other way around. So, usually we have to set one of the fruits down on a table - let's say the apple - then pass the orange from our right to our left hand, and then pick up the apple again with our right hand. That means we have to have a temporary holding area.

Either that, or we would have to juggle them, in which case the air is like the holding area.

What if we couldn't find any holding area at all?

Well, we cannot do that with fruit and our hands. But we can, inside the computer, with the wonderful XOR.

Now remember! Inside the computer we have ONLY two things: zero and one. OK, now watch the magic.

We have two storage places, A and B. For this example, we shall say they both should four bits - that is, four values which can be either zero or one.

Now, we want to reverse this, so that whatever is in A at the start will be in B at the end, and vice versa. I will show you how to do it, with just THREE repeats of the powerful XOR.

Step 1. Compute the value of (A xor B), and put that into A.
Step 2. Compute the value of (A xor B), and put that into B.
Step 3. Compute the value of (A xor B), and put that into A.

And now the values are swapped, just like the fruits were.

You don't believe me, do you?

OK, then I will go through it, step by step. You can follow along.

For our demonstration, inside A we will put this pattern: 0011
And inside B we will put this pattern: 0101

OK, here we go:

Before step 1: A= 0 0 1 1 B= 0 1 0 1

Step 1. Compute (A xor B) which is 0 1 1 0 and put that into A.

After step 1: A= 0 1 1 0 B= 0 1 0 1

Step 2. Now compute (A xor B) again: that is 0 0 1 1 and put that into B.

After step 2: A= 0 1 1 0 B= 0 0 1 1

Step 3. Now compute (A xor B) again: that is 0 1 0 1 and put that into A.

After step 3: A= 0 1 0 1 B= 0 0 1 1

Now look at what was in A and B back before step 1. You see?

Yes! they are swapped! And no extra storage, either!

Remember, you can use any values you like, and it will ALWAYS work. And we know that, because in our example we used every possible pattern in our A and B values - that's why I picked those two values to begin with! Because, as we said before, there are only two numbers. Another day we will see more.

Original source: from a library routine used by the old Control Data Corporation machine on which I learned (at an unnnamed school) back in the mid-1970s. (Thank you, Seymour Cray!)