Published: May 24, 2017
This post is about XOR bit manipulations. XOR is surprisingly capable of solving various algorithm problems.
XOR basics
Nothing is special. Here, I’m going to revisit what is XOR. XOR is exclusive or and often denoted as ⊕ or ^ (caret). It is a bitwise operation which works like this:
| x | y | x ⊕ y |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
XOR has properties of commutative and associative.
x ⊕ y = y ⊕ x
x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z
So what?
Well, to my surprise, there are many problems XOR really works to solve.
Once, XOR is applicable to the problem, a solution is extremely simple.
If a language supports features of map and/or reduce,
the solution may be one line of code.
I put some of such problems together here.
Lonely Integer
Problem: given an array of integers which forms pairs (appear twice) except one, find the integer apprear only once.
All other integers are pairs except one. So, this one is called a lonely integer. Sometime, the problem description is not like this straightforward. For example, checking drone ids when flying out and coming back, find a missing drone which didn’t return. Like this, some variations are out there.
From XOR basics above, XORing a pair of the same values gives zero. If all elements are XORed one by one, the answer is there.
Above returns 2.
Swapping values without any extra space
Problem: given two integers x and y, swap values without any extra space. Don’t use temp variable. Use only x and y.
At a glance, it looks tight. The requirement is no extra space. Commonly, swapping values uses one additional space to save a value. However, this is not the option from its requirement. Here comes XOR. The answer is extremely simple, just repeating x XOR y three times while assigning the result to x, y, then x.
x = x ⊕ y
y = x ⊕ y
x = x ⊕ y
Why this works? For example, let’s think values a and b are assigned to x and y:
x = a
y = b
x = x ⊕ y = a ⊕ b
y = x ⊕ y = (a ⊕ b) ⊕ b = a ⊕ (b ⊕ b) = a
x = x ⊕ y = (a ⊕ b) ⊕ a = a ⊕ b ⊕ a = a ⊕ a ⊕ b = (a ⊕ a) ⊕ b = b
After three times of XORs, x becomes b and y becomes a.
Below is an example to swap two elements in an array.
Above prints:
5 2 3 4 1
Addition without + / - operators
Problem: Add two integers x and y without using + / - operators.
Here again, XOR does the job. XOR has a memorable feature: XORing two values is equivalent to adding two values without a carry. To find whether the carry is there or not, AND is a good operator. Using this XOR’s feature, we can solve this problem.
Java code to solve this problem is in below:
Let’s see how this works. For example, a = 5 (101), b = 7 (111).
| a | b | carry = a & b | a = a ⊕ b | b = carry « 1 |
|---|---|---|---|---|
| 101 | 111 | 101 | 10 | 1010 |
| 10 | 1010 | 10 | 1000 | 100 |
| 1000 | 100 | 0 | 1100 | 0 |
The answer is 1100 in base 2, which is 12.
Nim Game
Nim is a simple two player game. At the beginning, n piles (called nim heap) of stones are there. Each pile has positive number of stones, for example, 5 piles of {2, 5, 10, 4, 6} stones. Players take turns removing one or more stones from any, but a single pile. The player who doesn’t have any stones left will lose the game.
The problem is which players, the first or second, will win the game.
The solution is pretty easy. Just XORing all number of stones in piles gives the answer. When the XORed result is zero, the second player wins, otherwise the first player. The hard part would be to understand why XORing all numbers leads to the answer.
Let’s think the state transition from S to T.
When the game goes S to T, one of piles will have the change which is certainly
a decrease in number of stones of that pile, say the pile k.
Suppose a previous state S and post state T are expressed:
S = X1 ⊕ X2, ⊕ …, ⊕ Xk, ⊕ …, ⊕ Xn
T = Y1 ⊕ Y2, ⊕ …, ⊕ Yk, ⊕ …, ⊕ Yn
Here’s some neat formula transitions.
T = T
T = 0 ⊕ T
T = (S ⊕ S) ⊕ T
T = S ⊕ (X1 ⊕ X2, ⊕ … ⊕ Xk, ⊕ … ⊕ Xn) ⊕ (Y1 ⊕ Y2, ⊕ … ⊕ Yk, ⊕ … ⊕ Yn)
T = S ⊕ (X1 ⊕ Y1) ⊕ … ⊕ (Xk ⊕ Yk) ⊕ … ⊕ (Xn ⊕ Yn)
T = S ⊕ 0 ⊕ … ⊕ (Xk ⊕ Yk) ⊕ … ⊕ 0
T = S ⊕ (Xk ⊕ Yk)
This means the next state will be XOR of the previous state and the number change. Accumulation of this state changes will be XORing all stone numbers at the beginning.
The Java code below solves the Nim game.
Above prints:
First Second