# Decoding the Universe: How the New Science of Information Is Explaining Everything in the Cosmos, from Our Brains to Black Holes

This Month
Stack Overflow 1

This Month
Stack Overflow 1

To me, the key intuitive aspect that distinguishes

XORfrom the other logical operators is that it is, orlosslessnon-lossy, meaning that, unlikeAND, andOR(and more similar toNOTin this regard), it is deterministcally reversible: You can exactly recover one of the input values given the rest of the computation history.The following diagrams illustrate that

ANDandOReach have at least one case where the state of one of the inputs is irrecoverable, given a certain value of the other input. I indicate these as "lost" inputs.For the

XORgate, there is no condition in which an input or output value cannot be recovered, given the rest of the computation history. In fact, there's a symmetry that knowingany two valuesof the tuple`(in0, in1, out)`

allows you to recover the third; specifically, whichever one you choose as the third value is theXORof the other two!This picture suggests that another way to think of the

XORoperation is as acontrollable NOTgate. By toggling one of the inputs (the upper one in the example above), you can control whether or not the other (lower) one is negated.Yet another equivalent view is that

XORimplements the positive-logicnot-equals(≠) function with respect to its two inputs. And thus also theequalsfunction (=) under negative-logic.In accordance with its symmetry and information-preserving properties,

XORshould come to mind for problems that require reversibility or perfect data recovery. The most obvious example is thatXORing a dataset with a constant 'key' trivially obscures the data such that knowing the key (which might be kept "secret"), allows for exact recovery.Preserving all of the available information is also desirable in hashing. Because you want hash values that maximally discriminate amongst the source items, you want to make sure that as many of their distinguishing characteristics as possible are incorporated, minimizing loss, in the hash code. For example, to hash a 64-bit value into 32 bits, you would use the programming language

XORoperator`^`

because it's an easy way to guarantee that each of the 64 input bits has an opportunity to influence the output:Note that in this example, information is lost even though

XORwas used. (In fact, ‘strategic information loss’ is kind of the whole point of hashing). The original value of`ul`

is not recoverable from the hash code, because you don't have two out of the three 32-bit values that where used in the internal computation. Out of the resulting hash code and the two values that wereXORed, you may have saved the result, but typically do not save either of the latter to use as a key value for obtaining the other.As an amusing aside,

XORwas uniquely helpful in the days of bit-twiddling hacks. My contribution back then was a way toConditionally set or clear bits without branchingin C/C++:On a more serious note, the fact that

XORis non-lossy has important information-theoretical implications for futuristic computing, due to an important relationship between information processing and the Second Law of Thermodynamics. As explained in an excellent and accessible book by Charles Seife, "Decoding the Universe", it turns out that the loss of information during computation has anexactmathematical relationship with the black-body radiation emanated by a processing system. The notion of entropy plays a central role in quantifying how information loss is expressed as heat. Noting that modern CPU development faces fundamental toleration limitations on thewatts/cm²of semiconducting materials, a solution (described by Seife) would be to design reversible, or lossless, computing systems, whereXOR's ability to preserve information—and thus shunt away heat—would play an invaluable role.