XOR tricks in Python

Why this matters

Some programming problems are written to test whether you know a clever bit trick. In real code, the trick is usually the wrong choice. The reason to learn it is to understand what the operator does, so that you can read the trick when you see it, and so that you know when it fails.

This lesson covers one operator, ^, which Python calls the bitwise XOR operator. Two tricks use it. The first swaps two integers without a third variable. The second finds the one value in a list that does not appear in a pair. Each trick rests on three facts about XOR, which you will see in the next section.

The lesson does not cover the other bitwise operators, & and |, which are taught in the bitwise operators lesson. It also does not cover shifts, which are taught in the shifts lesson, or the popcount method covered in the popcount lesson.

The idea: XOR works one bit at a time

A bit is a single digit, either 0 or 1. An integer is a row of bits. A bitwise operator takes two numbers and looks at them one bit position at a time. It makes a new number whose bits come from those pairs of bits.

XOR stands for "exclusive or". The name means: one or the other, but not both. For each bit position, the result bit is 1 when the two input bits are different, and 0 when they are the same.

Here is a small example with 8-bit numbers. The number 7 is 00000111 in binary, and 9 is 00001001. Lining them up and XORing position by position gives 00001110, which is 14 in decimal. Python does this on integers of any size, but the idea is the same.

The output is:

14 00001110

Three facts follow from the table, and both tricks in this lesson depend on them.

The first fact: XORing a value with itself gives 0. Every bit is the same as itself, so every result bit is 0. In Python, 5 ^ 5 is 0.

The second fact: XORing a value with 0 gives the same value. Every bit of 0 is 0, and a bit XOR 0 is the bit itself. In Python, 5 ^ 0 is 5.

The third fact: the order does not matter. a ^ b gives the same result as b ^ a. Also, when you XOR three or more values, the grouping does not matter, so (a ^ b) ^ c gives the same result as a ^ (b ^ c).

Combine the first two facts with the third and you get the core rule for the lesson. If you XOR together a list of values, every value that appears twice cancels out to 0, and the leftover is the value that appears once. The rest of the lesson shows what that rule buys you and where it breaks.

Trick 1: swap two values without a temporary variable

The usual way to swap two variables uses a third variable, called a temporary variable, to hold one value while the other is copied over. Python has a shorter way that needs no third name, because it builds both new values before it stores either one:

The output is:

a = 25 b = 12

The right side b, a is built first, as the pair (25, 12). Python calls a group like this a tuple: a fixed group of values in order. Then a is stored with 25 and b with 12. No third name is needed. This is the form to use in Python.

The XOR version does the same job with three lines. Each line uses the first fact or the second fact from the last section:

a = 12
b = 25
a = a ^ b
b = a ^ b
a = a ^ b

The next program prints the values before and after the XOR swap. The lines in the middle print the binary bits of 7 and 9, so you can see what happens to each variable.

The output is:

before: a = 12 b = 25
after:  a = 25 b = 12
binary of 7: 00000111
binary of 9: 00001001
x after x ^= y: 00001110 = 14
y after y ^= x: 7
x after x ^= y: 9

The labels in the output say x ^= y. That is shorthand for x = x ^ y, and it means the same thing. The program writes the long form so that you can read each step.

Worked example: following the swap step by step

Look at the swap of x and y in the program above. Start with x as 7 and y as 9.

Step one, x = x ^ y. The name x now refers to 7 XOR 9, which is 14 (00001110). The name y still refers to 9. The first value, 7, is now stored in neither name on its own. It survives inside 14, because 14 XOR 9 gives back 7.

Step two, y = x ^ y. This is 14 XOR 9, which is 7. So y now refers to the old value of x. The name x still refers to 14.

Step three, x = x ^ y. This is 14 XOR 7, which is 9. So x now refers to the old value of y.

After three steps, the values have traded places. No third name was used. The same three-step pattern works for any two integers, because XOR can always be undone by XORing again with the same value.

Why the trick matters less than it looks

The XOR swap is a good way to learn how XOR behaves. It is a poor way to write everyday code. The tuple swap a, b = b, a is shorter, easier to read, and works for any kind of value, not only integers. The XOR form works on integers and booleans, and it fails for one case that the next section shows.

The trap: swapping a value with itself

The XOR swap fails in one important case. If the two positions are the same storage place, the first step turns the value into 0, and the rest of the steps keep it at 0.

This case happens with lists. Suppose the two positions you are swapping are both the index 1. The program below does the XOR swap on values[1] and values[1], and then does the temporary swap on the same positions for comparison.

The output is:

[7, 0, 4]
[7, 9, 4]

The XOR version has lost the 9. The first line makes values[1] equal to 9 XOR 9, which is 0. The other two lines XOR zero with itself, so the value stays 0. The temporary version prints the list unchanged, which is the correct result for a swap of a position with itself.

Nothing in the XOR version warns you. The program does not fail, and the list has a value in every position, so the bug is silent. A value disappears. If your code might swap a position with itself, use the tuple swap, or check that the two indexes differ before the XOR lines run.

Trick 2: find the one value that has no pair

Now apply the core rule from the idea section. Suppose you have a list of numbers in which every value appears twice, except one value that appears once. You need to find that one value.

An easy way is to use XOR across the whole list. Start with 0. For each number in the list, XOR it into the running result. The pairs cancel to 0 as they go, and the single value is left at the end.

Here is a list with five numbers: 4, 1, 2, 1, 2. The value 4 is the one with no pair. The program below prints the running result after each number, so you can watch the cancellation.

The output is:

after  4 :   4 = 00000100
after  1 :   5 = 00000101
after  2 :   7 = 00000111
after  1 :   6 = 00000110
after  2 :   4 = 00000100
unpaired: 4

Read the trace. After the first 1, the running value is 5, which is 4 XOR 1. After the 2, it is 7. When the second 1 arrives, the 1 XORs out, leaving 6. When the second 2 arrives, the 2 XORs out, leaving 4. Only 4 remains, and it is the unpaired value.

Second example: a longer list in a different order

The order of the list does not matter, as the third fact promised. The next example has seven numbers, and the unpaired value is 42. The pairs appear in the middle of the list and at the start.

The output is:

sample2 xor: 42
empty xor: 0

The empty list returns 0. That is the value you start with, and it is the right answer only by accident, because an empty list has no unpaired value. A caller that needs to tell "no unpaired value" from "the unpaired value is 0" must check the length of the list first.

Writing the loop with functools.reduce

Python can write the same loop as one call. The function functools.reduce combines the items of a list two at a time, starting from the value you give it. The function operator.xor is the XOR operator as a function:

The output is:

42
0

This returns the same answers as the loop. Use whichever form your team reads more easily. The loop is the more common form in code that beginners read.

Third example: a large list with shuffled values

The first two examples used short lists that you can check by hand. This example builds a list of 1001 numbers. It holds 500 pairs of values, plus one extra number, and then shuffles the list. The random generator with a fixed seed gives the same sequence of numbers every time, so the code is repeatable.

The output is:

length: 1001
xor result: 123456789
matches lonely: True

The list is shuffled, so the pairs are spread across the whole list. The XOR still finds the one value, because the order does not matter. The three lines of output do not depend on the exact order the shuffle produced, so they are the same on any Python version that has the same random generator for randrange and shuffle. The exact positions in the list may differ between versions.

Comparison: a set uses more memory

A Python set is a collection that holds each value at most once. You can do the same job with a set. The idea is to add a value the first time you see it, and remove it the second time. What is left at the end is the unpaired value:

The output is:

{1, 3}

This version gives the answer you need when you want every value that has an odd count, not only the XOR of them. Its cost is memory. The set holds one entry for each value that is still open at that point in the loop, and in the worst case that is about as many entries as the list has values. The XOR version uses one integer of storage no matter how long the list is. That difference is the main reason to choose XOR for this job, and also the main reason it is not always the right choice.

Python sets also have the ^ operator, which gives the values that are in exactly one of two sets. It is the set version of XOR:

The output is:

{1, 3}

When not to use these tricks

Each trick is correct only under conditions. Here are the conditions where a plain approach is better.

For the swap, use the tuple swap a, b = b, a in Python. It is as short as the XOR form, it is easier to read, it works for any kind of value, and it does not fail when the two positions are the same. The XOR form is useful when you are reading old code that uses it, or when a problem explicitly asks you to swap without a temporary.

For finding the unpaired value, the XOR trick needs three conditions to hold at once. Every value except one must appear an even number of times. Exactly one value must appear an odd number of times. And the values must be integers, or other values that XOR works on. If any of these is false, the result can be wrong, and the program gives no error.

Here is the case where the first condition breaks. The list 1, 2, 2, 3, 3, 3 has two values with an odd count. The value 1 appears once and the value 3 appears three times. The XOR gives 2, which is neither of them. The mistakes section shows this in a real run.

If you need to know how many times each value appears, XOR cannot tell you. A count dictionary can. If the list can contain two unpaired values, XOR gives the XOR of the two values, not either one, and you need a different method, which is outside this lesson.

Common mistakes

Mistake 1: swapping a position with itself

The bug is shown in the trap section above. The fix is to use the tuple swap, or to check that the two indexes are different before using XOR. The check looks like this:

def swap_at(a, i, j):
    if i != j:
        a[i] ^= a[j]
        a[j] ^= a[i]
        a[i] ^= a[j]

Mistake 2: XOR on a string

The ^ operator works on integers, on booleans and on sets. It does not work on strings. Python raises an error for a string:

The output is:

Traceback (most recent call last):
  File "/path/to/main.py", line 3, in <module>
    s ^= t
TypeError: unsupported operand type(s) for ^=: 'str' and 'str'

The message names the operator and the two types. It means Python cannot find a meaning for ^= on those types. The fix is to use a different operation, such as + to join two strings, or to convert the values to numbers first.

Mistake 3: expecting ^ to mean a power

In math, a small raised number often means a power. Python does not do that with ^. The ^ symbol is always XOR, and the power operator is **. The program below shows the difference:

The output is:

1
8

The result of 2 ^ 3 is 1, because 10 XOR 11 is 01. To raise a number to a power in Python, use **.

Mistake 4: a swap function that does nothing to the caller

A beginner often writes a swap function that takes two integer parameters. The function runs, but the caller's variables are unchanged. Python gives the function its own names for the same values, and an integer cannot be changed in place. Assigning to the parameter names inside the function only changes the names inside the function. The program below shows this:

The output is:

inside swap: a = 2 b = 1
caller: p = 1 q = 2

The values swap inside the function, then the function ends and the names inside it are gone. A swap that works has to change the list element that holds the values. Lists can be changed in place, so the next program swaps two elements of a list inside a function:

The output is:

[30, 20, 10]
[30, 20, 10]

The first call swaps positions 0 and 2. The second call swaps position 1 with itself, and the check i != j stops the three XOR lines from running, so the list is unchanged.

Mistake 5: assuming a value appears an even number of times

The unpaired trick assumes that every other value appears in pairs. When that is not true, the answer is wrong and no error is shown. The next program adds a check, which uses a set that holds the values with an odd count, so you can see the cause.

The output is:

values seen an odd number of times: {1, 3}
xor result: 2

The set shows two values with an odd count: 1 and 3. The XOR result is 2, which is not in the set of odd-count values. The XOR cancelled the pairs correctly, but the leftover is the XOR of 1 and 3, and that is not either one of them. If your input might break the rule, check it first, or use the count-based approach.

Practice

Each exercise is followed by its answer. Try the exercise on paper or in a program before you read the answer.

Exercise 1: XOR of two small numbers. What is 6 ^ 10 in decimal? Write both numbers in 4-bit binary and XOR them position by position.

Show the answer

The binary of 6 is 0110, and the binary of 10 is 1010. XOR gives 1100, which is 12. You can confirm this with print(6 ^ 10), which prints 12.

Exercise 2: find the unpaired value by hand. For the list 5, 8, 5, 8, 3, what does the XOR loop return? Write the running result after each number.

Show the answer

The running values are 5, then 13, then 8, then 0, then 3. The last value is 3, which is the unpaired value. The program prints 3.

Exercise 3: swap two positions that might be the same. Write a function swap_at(a, i, j) that swaps a[i] and a[j] using XOR, and that leaves the list unchanged when i and j are equal.

Show the answer

The output is [30, 20, 10] and then [30, 20, 10]. The if check stops the three lines from running when the two indexes are the same. Without the check, a call like swap_at(arr, 2, 2) would set arr[2] to 0.

Exercise 4: what x ^= x does. For any integer x, what is the result of x ^= x? Explain which of the three facts makes the answer true.

Show the answer

The result is 0. The first fact says that XORing a value with itself gives 0. The expression 10 ^ 10 is 0, and the same holds for every integer. This is the fact that makes the unpaired trick work, and also the fact that breaks the XOR swap when both positions are the same.

Exercise 5: XOR on booleans. What do True ^ False and True ^ True print in Python? Explain the result in one sentence.

Show the answer

True ^ False prints True, and True ^ True prints False. For booleans, XOR means that the result is True when exactly one side is True. Unlike and and or, the operator always evaluates both sides, which the guards lesson covers in detail.

Summary

• XOR gives 1 for each bit position where the two input bits differ, and 0 where they match.
• Python's tuple swap a, b = b, a swaps two values with no temporary name, and it works for any kind of value.
• The three-line XOR swap also works on integers, but it sets the value to 0 when the two positions are the same.
• XORing a list of values cancels every value that appears an even number of times, which finds one value that appears an odd number of times.
• The unpaired trick gives a wrong answer silently when two values have an odd count. A set version lists every value with an odd count, and it uses more memory.