Xor - More Than You Wanted To Know

:date: 2026-01-16 20:57

Last month I realized that my programming language lacked a convenient way to do bitwise logical operations and so I added functions for them! This may seem like some freaky esoteric stuff but for serious programming (especially C programming) it comes up quite a lot. Especially when working on C I frequently need to test little logical constructions and having my extemporaneous calculator language be capable of trying out things like this on the fly can be very helpful.

What exactly is xor (or often XOR or even EXOR)? Xor is an especially interesting function. It is the logical exclusive OR function. In 1969, AI pioneer Marvin Minsky co-authored a book which claimed that a single layer perceptron in a neural network could not compute xor. This is technically correct. This was interesting because other logical functions were possible. Wikipedia has details. Some people extrapolated this to mean that neural networks were fundamentally limited  —  a pointless dead end. Those people were famously incorrect.

First, let's have a quick review of the three logical functions normal people are already familiar with. A logical function takes logical states (i.e. either true or false) as inputs and returns logical states as outputs. Imagine I am the CEO of a company and I will decide to do a venture or not (true or false on doing the venture). I have two advisers, Mr. A and Ms. B. If I require that both A says it is a good idea AND B says it is a good idea then my decision is A AND B. Alternatively, I could go with either A OR B  —  when one adviser saying it is a good idea is sufficient, then that would be A OR B. Easy. The other common logical operation is NOT. You can think of it as a filter for incompetent advisers; simply if A says do it, I don't, and if A says don't do it, I do. All of that is easy and we all know how to use those naturally.

So what's the deal with XOR? The first thing to note is that covering the other logical operators was on task. Don't get too bogged down with the details (unless you like that sort of thing) but you can actually build xor with them.

Or to see how it looks in (an HP48 style reverse) lisp here is the entire (Python) source code that composes the new binary xor function in my language showing that with the other operaters in place, xor was basically a bonus.

Of course that is gibberish to most people so let's return to a more human perspective to understand what this xor is really all about.

XOR works like this: if Mr. A and Ms. B both think an idea is bad, then we don't do it. Sensible enough. If A thinks it is good but B doesn't, we'll do it and also if B thinks its good when A doesn't we'll do it. That is just like regular OR. But the weird thing about xor is that if both Mr. A and Ms. B think it is a great idea, it will be rejected. Maybe the boss suspects untoward collusion or something like that. You can also suppose that both A and B agreeing is not "or-like" enough, hence the name "exclusive or".

Fortunately it is easy to spell out what all the important logic gates do (I just did) and the only one that's weird, xor, is easy to memorize. But to really understand it you have to have some sense of why you'd ever care about this weird quirky logic thing. It pops up more frequently than you might expect.

Let's start with a physical model. Imagine I'm designing some kind of storm water management system and I have two pipes from two flood prone regions, call them A and B. If neither region floods, ok, obviously nothing happens in the drain system (output is "false").

If A floods or if B floods, we want the drain system (at the bottom of the device) to politely handle the water.

The interesting part is if both regions flood simultaneously, this amount will overwhelm the drain system and we just want to dump all the water in the ocean (ahem San Diego).

That drain at the bottom of the diagram is essentially a fluidic XOR gate. And the drain to the ocean in the middle is actually an AND gate.

You can make entire computers with fluids out of devices like this but it is not really the most useful application of xor. It does demonstrate that the wierdness of xor's behavior can map to real world applications.

Perhaps the most common situation where xor logic is in our daily lives is a 3-way light switch where a single light is controlled by two switches. If it is true that switch A is up (1) and switch B is also up (1), then the light is off (1 XOR 1 = 0). If both A and B are down the light is also off (0 XOR 0 = 0). But if the switches are different, then the light is on (1 XOR 0 = 1; 0 XOR 1 = 1). My house wiring was installed by drunk children and I have two 3-way controlled lights  —  one of set is XOR as described and one is NOT XOR!

You can build a logic gate that does this using transistors and therefore you can etch them right on to semiconductors. That is important but let's explore xor's software applications which is where I personally encounter it.

If you xor a binary number with all 1s, you get the bitwise complement.

And...

This is the same as the NOT operator but interesting to note that NOT is achievable with xor.

A very common programming task is taking the contents of one variable and swapping it with the contents of another. Sure, Python has always had some superb syntax for this (a,b=b,a) but that underlines how important this is to programmers. In languages like Java and C++ you usually see this kind of thing.

Pretty comprehensible and very common. But there is another way! A way that interestingly does not require a temporary variable. In many languages the ^ is the xor operator.

Here is the short form. Kind of magical really.

This only works for integers but it is still pretty cool.

Note that this is mostly just a party trick. A modern Pythonic tuple reference swap is actually 4.5x faster than the XOR method, probably because it is a single cycle atomic operation. C++'s std::swap(A, B); is impressively twice as fast as the XOR method. So save this trick for when the memory concerns of a temporary variable are relevant. Or code obfuscation.

Very often one needs to reset a variable such as a counter back to 0 to restart a loop. How can you ensure that your counter is zero? The normal way is simple.

But there's another stranger way.

By feeding an xor function the same value for both inputs, you can be guaranteed the result will be 0. While that seems pointless to normal programmers, sometimes this can be useful. Remember that XOR is one of the most efficient operations a computer can do and is worth exploring when optimizing code. Normally your compiler knows all these tricks and behind the scenes it is very plausible that it could be generating machine instructions for zeroing out your counter like this.

This is an assembly language loop that does something 10 times. Note the first line.

A related thing xor can do is if you have some bits that you want to monitor for changes. You can take yesterday's bits and xor it with today's bits and if it doesn't turn out to be zero as described, something has changed.

Imagine you have a list of arbitrary binary numbers.

What would happen if you used AND twice?

You can see that there are 4 positions where all the bits are 1. You can see that if we keep doing this with more numbers, the trend is that the final answer will be all zeros after a while. What about OR?

A very similar deal except trending to all ones. But what about xor?

This is distinctive. It is also repeatable and these very basic logic operations are some of the cheapest to compute. This means that if you wanted to transmit the original three binary numbers and be pretty sure everything transferred correctly, you could transmit one extra number. That extra number is the xor checksum. The receiver then computes it from the three transmitted numbers, and it needs to match the one the sender computed too.

(Of course there are fancier checksums. The checksum standard RFC1071 says "...XOR is unsatisfactory for other reasons". But never says what those reasons are. While not especially robust, XOR operations are more robust than parity bits, which are used in error correcting memory.)

If you can manage to generate a very arbitrary checksum, there's almost a random property to it. The xor operation can be the "pseudo" in Pseudo Random Number Generators (PRNG). You could seed it with something really random or keep a replayable seed handy, but if you need mildly random numbers for very little computational cost, xor is a simple possibility.

An interesting use of xor is in (ancient) graphics programming to animate sprites. Let's focus on a simple black and white example that everyone is familiar with: the mouse pointer icon. When you move your mouse around, how does that work? The icon is mapped out with true (white) and false (black) bits in, yes, a bitmap. The screen that the pointer moves on is also a big map of bits. The mouse position is read from the HID (human input device) and a position for where to put the icon is determined. Then the bits that correspond to the size of the pointer icon's bitmap are read from the screen's bitmap. The pointer icon bits are then xor merged with the screen bits. This leaves the bits around the pointer arrow itself untouched. The magic of this and why it is useful in dynamic animated sprites like a mouse pointer is that when the move needs to happen you basically need to put the original bits back exactly as they were. With the (simple 2-bit black and white) setup I've described, you can reset to the original screen bitmap's bits by doing XOR on the pointer icon bits a second time. Like the toggle example, this toggles the presence of the pointer icon on, and then off.

This kind of xor based sprite rendering is pretty old fashioned. If you've been paying attention you'll recall that if the pointer icon's bit is white and the screen's bit is white, that will then be black. This means the sprite is always visible in every bit, but sometimes color inverted.

This works pretty well for selection boxes and some other items but practically deploying xor for graphics is a dying art. Still, the graphical application can stimulate ideas for other cases where something needs to temporarily rampage around memory.

Those are some of the interesting applications of xor. I've got one more interesting application to cover, but it is interesting enough to deserve its own post. Which I have now posted: https://xed.ch/blog/2026/0117.html