Is exclusive-or more computationally expensive than other logical connectives? (Related: it's also the only one that optimally preserves data.)

140 Views Asked by At

I expect this will be a very easy question to ask and answer. I noticed that XOR/XNOR seem to have a property I don't see in any other binary Boolean operation: in the general case, you need to know the values of both inputs to yield an output.

This is in contrast to, I believe, every other binary connective. For AND, if one of the inputs is false, the output is false, and all things being equal, you'll only have to check both inputs half of the time. Similar logic holds for OR, NAND, NOR, and IMPLIES.

In the real world, I know sometimes this makes no difference, particularly if you're talking about a certain physical circuit or something where all the work will always get done regardless. But certainly the general behavior in the computer science world is that once any of the inputs force a certain result on a logical operator, the computations intended for any remaining inputs are discarded, where possible.

The bottom line is that for XOR/XNOR, it seems like barring simplification, you must always carry out $2$ "units" of computation, one for each input, while for everything else, you'll only need $1.5$ units of computation on average. Even if the inputs aren't so well-distributed, AND/OR et al only pull even with XOR/XNOR in the absolute worst case.

I know this is a very minor thing, I'm just surprised I've been doing math/CS for so many years and I've never seen it come up. Basically, all I'm looking for is some confirmation of this property; if anyone can explain why it does or doesn't matter for e.g. low-level optimization tasks, I would be interested to hear that too.

Of course, if I've got something wrong here, please explain my error and I'll accept that as an answer too.


For what it's worth, I ran a quick spot check in Mathematica, one that barely involves computation, just a random element selection. Results below, where numbers given are seconds elapsed per operation (after running each function repeatedly for ten seconds).

enter image description here


Response to a couple comments below:

Loosely related to this observation is the property of XOR/XNOR wherein they perfectly transmit information, inasmuch as a 2-to-1 gate can. No other 2-to-1 gate does this. They all destroy information.

(Assume well-distributed random inputs for the following.)

Every output bit you get from an XOR gate eliminates precisely 2 of the 4 possible input pairs, on average. If you could then see one of the input bits, you would ascertain the other input with certainty. (This is essentially how RAID 5 and similar tricks work; you can have two drives worth of data saved across three drives, all XORed, and any drive can be replaced with no data loss.)

Whereas if you have a NAND, $\frac{1}{4}$ of the time its output would be $0$, telling you its inputs are exactly $(1,1)$. The other $\frac{3}{4}$ of the time, the NAND output would be $1$, which only tells you the inputs aren't both $1$. If you go on and examine one of the input bits, half the time it would be it would be $1$, implying the remaining bit is $0$; the other half it would be $0$, giving you no information about the remaining bit, which would then need to be checked as well.

So the number of bits you need to inspect (if you start with the output) to know the full state of the NAND gate is, on average, $$\frac{1}{4}\cdot 1+\frac{3}{8}\cdot 2+\frac{3}{8}\cdot 3 = \frac{17}{8} = 2.125.$$

Compare to the XOR case, which is always simply $2$ bit checks required, since any two bits determine the third.

So yes, while XOR isn't functionally complete like NAND, it is more expressive in the narrow sense that it's an inherently cleaner transmitter of information. (Incidentally, discarding or disregarding data actually seems to be a fundamental requirement to enable full Turing-complete computation.)