Wait, what is XOR?

XOR is short for Exclusive OR (we use the X, instead of EOR, because X is cooler). XOR has a lesser known, less cool friend, Inclusive Or (IOR).

These two names come from an issue in English (and many other languages), where we use ‘or’ for two different purposes. The difference between these two is when someone talks about “A or B”, are you allowed both A and B, or just one or the other? In maths and computing, where we need to be more exact, we separate these two cases into XOR (you cannot have both) and IOR (you can have both).

To hopefully make this clearer, let’s consider a couple of real-world examples. I decided to pick a couple of examples from the Disney World website. Let’s begin by picking one of the rules of Disney World: you cannot “harass or harm wildlife”. Reasonable-sounding rule! If you started kicking a duck while also insulting it, you would be both harassing and harming wildlife. This is clearly an ‘inclusive’ or. If you tried to claim you were not “harassing or harming wildlife, I’m doing both!”, you would still get kicked out of the park.

On the other hand, over in the Refreshment Corner, the “All-Beef Hot Dog Basket” comes with a “Mandarin Orange or a Small Bag of Chips”. Here, the ‘or’ is exclusive: you can have an orange, you can have chips, but you cannot have an orange and chips! No matter how much you pointed at the person being dragged out of the park for duck harassment and harming, Disney are not going to agree their rules are inconsistent.

How do we know if an ‘or’ is inclusive or exclusive? There are some general rules, but often you just have to know by context. However, because we want to be clear when using computers, we are going to use ‘XOR’ when we mean “A, or B, but not both”.

What is a logical XOR?

A logical XOR takes two true/false values and returns true when exactly one of the two is true. We can write this out as a table:

A	B	A XOR B
false	false	false
false	true	true
true	false	true
true	true	false

One useful way to think about XOR: A XOR B is the same as asking “are A and B different?” If they are different, the result is true. If they are the same, the result is false.

Now you might be thinking, wait, isn’t this just “not equals”? Why the heck is it called XOR? You would be entirely right. Honestly, I’d call it not equals. But it makes more sense to call it XOR once we look at the bitwise version, coming up next.

What is the XOR bitwise operator?

In most programming languages, the ^ operator performs a bitwise XOR. This means it takes two integers, lines up their binary representations, and applies logical XOR to each pair of bits independently.

For example, let’s XOR the numbers 12 and 10:

  12 = 1100
  10 = 1010
  ----------
  ^  = 0110 = 6

Each column is just a logical XOR: 1 XOR 1 = 0, 1 XOR 0 = 1, 0 XOR 1 = 1, 0 XOR 0 = 0.

Bitwise XOR has two particularly useful properties:

1. Self-inverse: a ^ a == 0 for any value a. Every bit cancels with itself.
2. Identity: a ^ 0 == a. XOR with zero changes nothing.

Combining these, if we compute a ^ b ^ b, the two bs cancel and we get back a. This works the other way too: a ^ b ^ a gives us b.

That cancellation is the ingredient behind the XOR swap trick, which I have discussed at entirely too much length in another post.