XOR tricks

Why this matters

Many programs need to swap two values. A sorting routine swaps neighbouring items. A game swaps two cards. The usual way is to copy one value into a spare variable, called a temporary, and then move the values around. Programmers have known for a long time that a bitwise operator can do the same job with no spare variable. The operator is ^, called XOR.

XOR also solves a classic puzzle. You are given a list of numbers where every value appears twice except one. You need to find the single value. You could count each value in a map, but XOR finds it in one pass and with no extra memory.

These tricks are clever, and that is the reason to be careful with them. They fail on some inputs, they are harder to read than the plain version, and they give no speed gain in ordinary code. This lesson shows the two tricks step by step, then shows when to leave them out. It builds on the bit operators from the earlier lessons in this module, such as & and <<. It does not repeat the precedence rules, which are covered in the precedence trees lesson, although one precedence trap appears in the mistakes section.

What XOR does, one bit at a time

Numbers are stored in binary, as bits. A bit is a single digit that is either 0 or 1. The bitwise operators work on each bit position separately. XOR, written ^ in C++, gives a 1 in a position when the two input bits are different, and a 0 when they are the same.

Read the table as "XOR is 1 when exactly one side is 1." The name means exclusive or. The word "exclusive" means that one of the two options is picked, not both.

Here is a whole-number example. The number 12 in binary is 01100. The number 25 is 11001. Put them one above the other and apply the table to each column, from left to right:

   01100   (12)
 ^ 11001   (25)
   -----
   10101   (21)

The first column has 0 and 1, which differ, so the result is 1. The second column has 1 and 1, which are the same, so the result is 0. Continue to the last column and you get 10101, which is 21 in decimal. So 12 ^ 25 is 21.

Four rules follow from the table. You do not need to memorise them as rules. Just check them with the example above.

• x ^ x is 0, because the two bits in every column are the same.
• x ^ 0 is x, because each column of zeros leaves the other bit unchanged.
• The order does not matter. a ^ b and b ^ a give the same result.
• Grouping does not matter. (a ^ b) ^ c and a ^ (b ^ c) give the same result.

The last two rules mean you can XOR a list of numbers in any order and still get the same answer. The first two rules are the ones the tricks depend on. Any value XORed with itself cancels out, and XORing with zero changes nothing.

Swapping two variables without a temporary

First, the ordinary swap, so you can compare. Suppose a holds 12 and b holds 25, and you want them to trade places.

The variable temp is the temporary. It saves the old value of a before a is overwritten. Without it, the old value of a would be lost the moment a = b runs.

The XOR version needs no temp. It uses three lines, each of which changes one variable with ^=. The operator ^= means "XOR into this variable": a ^= b is the same as a = a ^ b.

The output is:

start a=12 b=25
step1 a=21 b=25
step2 a=21 b=12
step3 a=25 b=12

Look at each step with the binary in mind. In step 1, a becomes 12 ^ 25, which is 21. The variable a now holds a mix of both numbers, and the value of b is still 25. In step 2, b becomes 25 ^ 21. Since a contains 12 ^ 25, XORing it with 25 removes the 25 and leaves 12. So b now holds 12. In step 3, a becomes 21 ^ 12. The 12 cancels the 12 mixed into a, and the 25 is left. So a holds 25.

Here is the same trace as a table, to make the pattern easy to follow:

The reason it works is that after step 1, a holds x ^ y, where x and y are the original values. In step 2, b becomes y ^ (x ^ y), which is x, because y cancels. In step 3, a becomes (x ^ y) ^ x, which is y, because x cancels. Each cancellation uses the rule that a value XORed with itself is 0.

For a quick check, the same idea also works with int a = 6, b = 3. Step 1 makes a 5. Step 2 makes b 6. Step 3 makes a 3. You will work this out yourself in the practice section.

In real code you should use std::swap from the <utility> header. It does the same job, it is easy to read, and the compiler generates code that is just as fast. The XOR version is worth knowing because you will see it in older code and in interview questions. The next section shows the one case where the XOR version breaks badly.

The swap that erases a value

The XOR swap only works when the two variables are different places in memory. If both names point to the same place, the first line makes that place 0.

Think of two boxes labelled a and b. If you put the same box under both labels, the first step does box ^= box, which is 0 in every column. The value is gone.

This matters most with arrays and vectors, where two indexes can point to the same element. Here is a short program that swaps two elements. The function xor_swap is written with references, so it changes the elements in place.

The output is:

before v[1]=9
after same index v[1]=0
different index: w[0]=7 w[2]=5

When i and j are both 1, the call swaps v[1] with itself. The first line becomes v[1] ^= v[1], which sets it to 0. The next two lines cannot bring the value back, because every later step XORs with the same 0. The second call uses different positions, so it works. With the temporary version, a swap of an element with itself is harmless. With the XOR version, it destroys data. Sorting code can call a swap with i and j equal, so this case is not rare.

Finding the single unpaired value

Now the second trick. Suppose you have a list of numbers. Every value appears exactly twice, except one value, which appears once. You need the value that appears once.

Start with a small list: 4, 1, 2, 1, 2. The value 4 is the one with no pair. The values 1 and 2 each appear twice.

XOR every number together, starting from 0. Use the rules from earlier. Since 0 XOR anything is that thing, the start value of 0 does nothing. Since every pair cancels, each pair leaves nothing behind. Here is each step:

start:  0
0 ^ 4 = 4
4 ^ 1 = 5
5 ^ 2 = 7
7 ^ 1 = 6
6 ^ 2 = 4

Each value is XORed in once. The second 1 and the second 2 each undo the first copy, so the running result returns to the value that has no partner. The final answer is 4.

The same result follows from grouping the numbers by pair. XOR is order-free, so you may group the numbers in any way:

4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4

Each pair is 0, and the single value is left alone. This is the whole idea. Pairs cancel and the single value survives.

The code uses std::accumulate from <numeric>. That function walks a range and combines every element with an operation. The operation here is bit_xor, from <functional>, which is the function version of ^.

The output is:

a: 4
b: 5
c: 6

The list c has one value and no pairs, so the answer is that value. The function needs one pass over the list and uses one int of extra storage. A map that counts each value would use memory that grows with the number of distinct values.

Empty input

If the list is empty, the function returns 0. That is the start value of the XOR. It is also a normal number in the list, so the caller cannot tell "no list" from "the single value is 0". Check the list is not empty before you call the function, or return a std::optional (a value that can be empty) if your code has to tell the two cases apart.

The output is:

9
0

The second 0 means "nothing was found", and it is the same as a list whose single value is 0. The code has no way to tell the difference.

A harder case: two unpaired values

The next example is harder. Now there are exactly two values that appear once. Every other value appears twice. The XOR of everything gives the XOR of the two singles, which is p ^ q, where p and q are the two single values. That result alone does not tell you p or q. The trick needs one more idea.

The idea is this. Since p and q are different, their XOR has at least one 1 bit. That bit is a position where p and q differ. Pick one such bit. Split the whole list into two groups by that bit: numbers with a 1 in that position go in one group, and numbers with a 0 go in the other. Now p lands in one group and q lands in the other. Each pair lands in one group, because a pair has the same value both times. Each group is then the single-value problem again, so XOR each group on its own.

The bit to use is the lowest one set in p ^ q. The expression both & -both keeps only that lowest 1 bit. The minus sign on an int gives the two's complement negation, which is a standard way of storing negative numbers. You do not need the details here. The fact to remember is that x & -x leaves only the lowest 1 bit of x.

Here is a full walk through the list 2, 4, 6, 4, 8, 2, 10, 6. The pairs are the two 4s, two 2s and two 6s. The singles are 8 and 10.

First, XOR everything. The pairs cancel, so the result is 8 ^ 10, which is 1000 ^ 1010 = 0010, the number 2. The lowest set bit of 2 is itself, so the split bit is 2, written 0010.

Second, split by that bit. A number goes in the first group if it has a 1 in the position worth 2. The numbers 2, 6, 2, 10 and 6 have that bit set, so they go in the first group. The numbers 4, 4 and 8 do not, so they go in the second group.

Third, XOR each group. The first group holds the pairs of 2s and 6s, which cancel, and the single 10, so it gives 10. The second group holds the pair of 4s and the single 8, so it gives 8.

The output is:

10 8
3 5

The function returns the two values, but not in a fixed order. The first returned value is the one that has the split bit set. For the list 3, 5, the XOR is 6, which is 110. The lowest set bit is 010, the number 2. The value 3 has that bit set and 5 does not, so the output is 3 5. The order happened to be sorted in this example. Do not rely on it. If the caller needs a fixed order, sort the two results before using them.

The function reads the list twice and uses a fixed amount of extra storage. It does not depend on how many numbers there are, only on how many bits an int has.

Common mistakes

These are mistakes that beginners and experienced programmers make with these tricks. Where the compiler or the program reports something, the text shows the real message or output, so you can recognise it.

Mistake 1: using ^ for a power

In maths, people sometimes write 2^3 to mean 2 to the power 3, which is 8. In C++, ^ is always XOR. The expression 2 ^ 3 is 1, because 10 XOR 11 is 01. g++ 15 warns about this pattern when -Wall is on:

warning: result of ‘2^3’ is 1; did you mean ‘1 << 3’ (8)? [-Wxor-used-as-pow]

To get a power of two, use a shift, such as 1 << 3, which is 8. For other powers, use pow from <cmath>, which works on doubles.

Mistake 2: XOR on a double

XOR works on whole numbers only. A double holds a fraction, and the bits of a fraction do not have the same meaning as the bits of a whole number. The compiler refuses the code:

double a = 1.5;
double b = 2.5;
a ^= b;

The g++ error is:

error: invalid operands of types ‘double’ and ‘double’ to binary ‘operator^’

This applies to float too. The XOR tricks only work on int, unsigned int, char and the other integer types.

Mistake 3: precedence

The operator ^ has lower precedence than ==. Precedence decides which operator is done first when there is no bracket. So x ^ y == 0 is read as x ^ (y == 0), not as (x ^ y) == 0. The first expression compares y with 0 first, which gives a true or false value, and then XORs that with x. The result is almost never what was meant.

The output is:

5 1

The first result is 5, which is 5 ^ 0, because y == 0 is false and counts as 0. The second result is 1, which is true, because x ^ y is 0. Always put brackets around an XOR that sits next to a comparison. g++ warns about this case with -Wall, using the message suggest parentheses around comparison in operand of ‘^’.

Mistake 4: using the trick when a value appears three times

The find-single trick depends on pairs cancelling. A value that appears three times does not cancel. It leaves its value behind, as if it appeared once.

The output is:

result: 2

The correct answer is 7, because 5 is not the single value here, and 7 is. But the XOR gives 5 ^ 5 ^ 5 ^ 7, which is 5 ^ 7 after the pairs of 5 cancel. That is 101 ^ 111 = 010, the number 2. The trick is only for "every other value appears an even number of times". A list where some value appears three times needs a count of each bit, or a map of counts. The swap trick and the single-value trick both fail quietly, with no error message, so check the assumptions before you rely on them.

Mistake 5: swapping an element with itself

This was shown in the swap section. When two indexes can be equal, guard the XOR swap with a check.

void swap_pair(vector<int>& v, size_t i, size_t j) {
    if (i == j) return;
    v[i] ^= v[j];
    v[j] ^= v[i];
    v[i] ^= v[j];
}

The guard costs one comparison. Without it, swap_pair(v, 1, 1) sets v[1] to 0.

When not to use these tricks

The tricks are correct in the cases described above, but they are a poor choice in most ordinary code. Here is each reason, with what would actually happen.

• Readers have to work out the trick. A three-line std::swap or a three-line temporary swap is read at a glance. An XOR swap needs a reader to trace the cancellations. A bug in the code costs more time to find than it saves in memory.
• The compiler does the same job. With g++ 15 at -O2, a common optimisation level, on x86-64, the temporary version and std::swap generate four move instructions. The XOR version generates six instructions, and all six read or write memory. In normal programs this is not a speed gain, and it can be a loss.
• The swap trick hides a bug when the two names may refer to the same place. The result is a value of 0 with no error. A temporary swap does not have this problem.
• The single-value trick needs every other value to appear an even number of times. With other counts it returns a wrong answer silently, as shown in mistake 4.
• The single-value trick does not work for types with fractions. It cannot run on double at all, so the compiler stops the build.
• A map or a sort is often clearer. If a list is small or the code is read by many people, a plain count with unordered_map or a sort followed by a scan will be easier to check. Use the trick when the input rules are fixed, the time or memory limit is tight, and a comment explains the reason.

Use the trick when all of these hold: the data is whole numbers, the rules of pairs are guaranteed, the values cannot be the same place, and a comment in the code says why XOR was chosen.

Practice

Exercise 1. The code below swaps a and b with XOR. What does it print?

int a = 6;
int b = 3;
a ^= b;
b ^= a;
a ^= b;
cout << a << " " << b << endl;

Show the answer

It prints 3 6. After the first line, a is 5, which is 110 ^ 011. After the second line, b is 3 ^ 5, which is 6. After the third line, a is 5 ^ 6, which is 3.

Exercise 2. Find the single unpaired value in the list 9, 2, 9, 7, 2 using the XOR of all values.

Show the answer

The answer is 7. The pairs of 9s and 2s cancel, and 7 is left.

Exercise 3. Compute 5 ^ 3 in binary, then in decimal. Then say what 2 ^ 3 prints in C++.

Show the answer

The binary of 5 is 101 and the binary of 3 is 011. Their XOR is 110, which is 6. In C++, 2 ^ 3 is XOR, not a power, so it prints 1.

Exercise 4. The list 5, 5, 5, 7 does not give 7 when you XOR all of it. Explain why, using the rule for pairs.

Show the answer

The value 5 appears three times, which is an odd number, so it does not cancel. The value 7 appears once, which is also odd. Two values are left over, and the XOR of them is 5 ^ 7, which is 2. The find-single trick only works when every value except one appears an even number of times.

Exercise 5. Write a function void swap_pair(std::vector<int>& v, std::size_t i, std::size_t j) that swaps v[i] and v[j] with XOR, and that is safe when i and j are equal. Test it with the vector 1, 2, 3 by swapping index 0 with index 0, then index 0 with index 2.

Show the answer

The output is 321. The first call returns at once because the indexes are equal, so nothing changes. The second call swaps the first and last elements, giving 3 2 1.

Summary

• XOR (^) gives 1 in each bit position where the two inputs differ. Any value XORed with itself is 0, and any value XORed with 0 is itself.
• Three XOR steps (a ^= b; b ^= a; a ^= b;) swap two integers without a temporary, but they set both to 0 when the two names refer to the same place.
• XORing every value in a list leaves the one value that appears an odd number of times, when every other value appears an even number of times.
• For two single values, split the list by one bit where they differ, then XOR each group.
• XOR works only on integer types. Using ^ on a double is a compile error, and writing 2^3 for a power gives 1, not 8.
• Prefer std::swap in ordinary code, and a count or a sort when the input rules are not guaranteed.