XOR

Posted on April 19, 2015

In this post we will talk about xor. Xor is a logical operator that outputs true when the two input values are different, and false otherwise. It is usually simbolized with \(\oplus\).

Given that we can represent natural numbers (and integers) in binary, we can also do bitwise xor, i.e., xoring bit by bit. Then, for example \(5 \oplus 3 = 101_2 \oplus 011_2 = 110_2 = 6\)

Properties

First we should see some of the properties of \(\oplus\).

All of these are really simple to prove. Note that these properties implies that \((\mathbb{N}, \oplus)\) is an abelian group. More on this later.

OLOLO

To start appreciating how useful \(\oplus\) is, we can do this spoj problem. Obviously, spoiler alert, I’m going to solve it.

Onotole has a lot of pyani. Each pyani has a number, writing on it. Pyanis with equal numbers are indistinguishable. Onotole knows everything, so, he knows that each pyani appeared twice, and only one pyani is unique. He wants to get вздръжни эффект, and he needs the unique pyani. Given the list of pyanis denote which one of them appeared once (it is guaranteed that other pyanis appeared twice).
Input
First line of input contains number of pyanis N<=500 000. Next N lines contain a single positive integer 1 <= Pi <= 10^9.
Output
Output one positive integer on pyani, which appeared once.

Solution

Suppose the stream of positive integers is something like this \((p_1, p_2, …, p_i,…, p_N)\), where every element is repeated twice, except \(p_i\)that is repeated once.

Now we can xor all those positive integers, like

\[p_1 \oplus p_2 \oplus … \oplus p_i \oplus …\oplus p_N\]

As \(\oplus\) is commutative and associative, we can group every two elements that are equal toghether, so we end up with

\[(p_1 \oplus p_1) \oplus … \oplus (p_N \oplus p_N) \oplus p_i\] \[ = 0 \oplus … \oplus 0 \oplus p_i\] \[ = p_i\]

So all we have to do is xor all the numbers, and the final result is the number we are looking for. This algorithm takes time \(O(n)\) and space \(O(1)\).

Devil’s Chessboard

Consider a standard chessboard with 64 squares. The Devil is in the room with you. He places one coin on each of the 64 squares, randomly facing heads or tails up. He arbitrarily selects a square on the board, which he calls the Magic Square. Then you have to flip a coin of your choosing, from heads to tails or vice versa. Now, a friend of yours enters the room. Just by looking at the coins, he must tell the Devil the location of the Magic Square. You may discuss any strategy/algorithm with your friend beforehand. What strategy do you use to do this?

Think about the problem before continuing reading. It seems actually impossible, but with the information we now have about xor it should be as easy as pie.

Solution

Number all the squares, from 0 to 63. Let \(D\) be the square that the Devil chose. Let \({H_i}\) be all the squares such that its coin is heads and \(H = H_1 \oplus … \oplus H_n\).

Then we can solve for \(X\).

\[H \oplus X = D\]

Why this?

Suppose \(X\) is tails. Then we flip that coin, and then all our friend has to do is to xor all the squares with heads, and the result is \(D\), and we are done.

Now suppose \(X\) is heads, then we flip it and it works as before. Because \(H = H_1 \oplus … \oplus X \oplus … \oplus H_n\), then \(H \oplus X = D \), again, because the \(X\) cancels out.

The end.

But we can generalize this. If the number of squares is a power of \(2\), then the equation \(G \oplus X = D\) will always have a solution in \({0,…,2^n-1}\) (if you don’t get this, think about the bits) , so we can solve the problem.

But what if the number of squares is not a power of two? I don’t know, it is a nice problem to think about. For a start, if the number of squares is 3, then there is no solution, i.e., the devil always wins, it can be checked case by case.

Assembly

If you ever programmed in assembly, you must have seen this instruction

xor rax, rax

and you must have wondered why it was like that instead a more sane

mov rax, 0

With a little gdb and googling, one can find out that xor rax, rax compiles to 48 31 c0 in machine code, while mov rax, 0 compiles to b8 00 00 00 00.

So the first instruction not only generated less code, it is faster to execute, because the CPU has to fetch less data from memory. This is another very used advantage of xor.

Game Theory

In Combinatorial Game Theory there is a very important function called the Sprague-Grundy function.

\[g(x) = mex\left\{g(y), y \in F(x)\right\}\]

Where \(mex\) is the minimum excluded natural of the set and \(F(x)\) the all the possible following positions from \(x\).

One can show (I won’t do it here, you can check it in [1]) that if a position \(x\) in a game is a P position, i.e. the next player loses, then \(g(x) = 0\) and viceversa.

Now, the important thing about this function is the concept of sum of games. Some games are very hard to analyze on their own, for example Nim. So one can think about Nim as several Nims with only 1 heap being played simultaneously.

This concept is called sum of games, and if \(G_1\) and \(G_2\) are games the game of playing them simultaneously is \((G_1, G_2)\).

The Sprague-Grundy theorem says that \(g((G_1, G_2)) = g(G_1) \oplus g(G_2)\). Yes, that is a xor, surprisingly enough — though in this context it is called Nim-sum. Again for a proof you can see [1], but it is very simple.

XOR cipher

Using the same properties we used over and over again throughout this post, we can desing a cipher to encode messages. Suppose you have your message written in a chain of 0’s and 1’s called \(M\). You can choose a random chain of 0’s and 1’s of the same length \(X\) (the key), and bitwise xor them, so \(E = M \oplus X\).

So \(E\) is the encoded message. Then, if you want to decode it, all you have to do is xor it with \(X\). \[E \oplus X = (M \oplus X) \oplus X = M \oplus (X \oplus X) = M \oplus 0 = M\]

The bad thing about this cipher is that if an attacker gets \(M\), the message, and \(E\), the encoded message, he can very easily get the key, simply because \[M \oplus E = M \oplus (M \oplus X) = X\]

Next there is a simple program that implements the cipher

void xor_cypher(char* msg, const char* key, int n) {
  int i;
  for (i = 0; i < n; i++) {
    msg[i] ^= key[i];
  }
}

Other interesting-but-not-so-useful properties

References

[1] Ferguson, T. Game Theory

[2] Conway, J. On Numbers and Games