The XOR trie idea in Python

Why it matters

A trie does not have to store letters. It can store the bits of a number, which are the zeros and ones that make up its binary form. That idea solves a classic interview question: given a list of numbers, find the two whose XOR is largest. The brute-force answer checks every pair, which is too slow for a large list. The trie answer takes one pass over the numbers and about 31 steps for each one, no matter how many numbers there are. The same structure also counts pairs below a limit and answers queries about one number against a set. This lesson builds all three, from the ground up.

Bits: numbers written with only zeros and ones

A computer stores a number as a row of bits, each of which is 0 or 1. A bit is a single binary digit. Just as the decimal digits of 25 mean 2 tens and 5 ones, the binary digits of a number mean sums of powers of two. The rightmost bit is worth 1, the next is worth 2, the next 4, then 8, 16, and so on. Each position is double the one to its right.

So the binary number 11001 means one 16, one 8, zero 4s, zero 2s and one 1. Add them: 16 + 8 + 1 = 25. The number 5 is 101, which is one 4 and one 1, so 4 + 1 = 5.

In Python, the built-in format(n, "b") gives the binary form of a number as a string, without the leading zeros. The bin(n) function does the same job but adds the prefix 0b. Python's ^ operator is XOR, and it works on every bit position at once. XOR gives 1 for a bit position when the two input bits are different, and 0 when they are equal. Here is the full table for one bit:

So 5 ^ 25 lines up the two binary forms and applies the table to each column. The form of 5 is 00101 when padded to five digits, and the form of 25 is 11001. Column by column, the results are 1, 1, 1, 0, 0, which reads 11100. That is 16 + 8 + 4 = 28.

The program below prints the binary form of two numbers, and then their XOR.

The program prints:

5 in binary: 101
25 in binary: 11001
5 ^ 25 = 28 (binary 11100)

Notice that format drops leading zeros, so 5 prints as 101 and not as 00101. The answer is 28, which matches the column reading above.

XOR has a property that matters later: a bit of the result is 1 exactly when the two input bits are different. So if you want a large XOR, you want the partner number to differ from your number in as many high bits as possible.

Python's ^ is not a power. The expression 2 ^ 3 is 1, because it XORs the bits of 2 (10) and 3 (11). To raise a number to a power, Python uses **, so 2 ** 3 is 8.

Why the brute force is too slow

The direct way to find the largest XOR of two numbers is to try every pair. For each pair, compute the XOR and keep the largest. With n numbers there are n * (n - 1) / 2 pairs. The itertools.combinations function gives every pair of items from a list, once each, so the brute force is short. The first loop version below shows the steps, and the second version uses combinations and returns the same answer.

The program prints:

28
28

The answer is right, but the method does not scale. With 100,000 numbers, the pair count is about 5 billion. Each pair takes several steps in Python, so the program would run for a very long time, far longer than a second. The brute force is still valuable, though. It is short and obviously correct, so you use it to check a faster method on small inputs. You will do exactly that after the trie version below.

The key insight: high bits matter most

The faster method starts from one fact about binary numbers. A 1 in a high bit is worth more than every bit below it combined. Look at bit 3 (worth 8) and the bits below it (worth 4, 2 and 1). Their largest total is 4 + 2 + 1 = 7, which is less than 8. So once you can make bit 3 of the XOR equal to 1, you should do it, whatever the lower bits do.

This is a greedy idea. A greedy method makes the best choice at each step, based on what it knows now, and never goes back. For this problem the greedy choice is simple. Look at the highest bit first. For your number x, the best partner y has the opposite bit at that position, because that gives a 1 in the XOR. If any stored number has the opposite bit there, choose it. Then move to the next bit and repeat, but only among numbers that agree with the choices you already made.

Think of a game of twenty questions where you always answer the opposite of yourself. Each question cuts the field, and you choose the question that forces the most difference. The greedy choice is correct because the first bit where you can differ always decides the answer, however the lower bits fall.

The binary trie

To make the greedy choice fast, store the numbers in a binary trie. This is the same structure as the letter trie, with two children on each node instead of 26. The children are for bit 0 and bit 1. A number is a path of 31 steps, one bit per step, from the highest bit to the lowest. We use bits 30 down to 0, which covers every whole number from 0 up to 2,147,483,647. That is the largest value a 32-bit signed integer can hold, and it is the range many programs use. A later section shows what happens to larger values in this design.

Insert a number by walking its bits from high to low. At each bit, go to the child for that bit, creating it if needed. Searching for the best partner of x walks the same way, but at each bit it prefers the child with the opposite bit. If that child exists, it takes it and sets that bit of the answer to 1. If it does not, it must take the child with the same bit, which adds nothing.

Each node holds two children. In Python a node can be a small class with one list of two slots, children, where index 0 is the child for bit 0 and index 1 is the child for bit 1. A slot holds None when no child exists.

The example below shows the trie for the three numbers 1, 2 and 5, written with three bits each. The numbers are 001, 010 and 101. The walk for x = 2 is 010. Here is the walk, step by step. The number x is 010. At the top bit (bit 2), x has 0, so the opposite is 1. The trie has a child 1, so take it. The XOR bit at position 2 is 1. At bit 1, x has 1, so the opposite is 0. The node 10 has a child 0, so take it. The XOR bit at position 1 is 1 again. At bit 0, x has 0, so the opposite is 1. The node 101 has a child 1, so take it. The XOR bit at position 0 is 1. The walk ends with 111, which is 7. The partner is 101, which is 5, and 2 ^ 5 is 7. So the greedy walk found the best partner for 2 without comparing it to every number.

Now the complete solution. It builds the trie for all the numbers, then runs the greedy walk for each number, keeping the best result. The expression (x >> bit) & 1 reads one bit of x: >> shifts the bits right by bit places, and & 1 keeps only the lowest one.

The program prints:

28

That is the same answer as the brute force. Run the slow, obvious version and the fast version on many small inputs, and check that they match. That agreement is the best way to test a clever method.

Two details in best_xor_with deserve attention. The line result |= 1 << bit sets bit bit of the answer to 1. The expression 1 << bit is the number with only that bit set, and |= turns that bit on without changing the others. The else branch, node = node.children[b], covers the case where no opposite child exists. That case can only happen when the same-bit child is present, which the next section explains.

Why the same-bit child always exists

The walk needs node.children[b] to exist when node.children[want] is missing. Otherwise node would become None, and the next time the loop reads node.children Python would raise an AttributeError. The reason it never does is simple. Every node in the trie exists only because some number passes through it. So every node that is not a leaf has at least one child. If the opposite child is missing, the other child must be the one present. This is a property of the trie, not something the code has to check.

Worked trace: the greedy walk for 25

Before the code, follow one walk by hand, so the greedy rule is clear. Use the six numbers from the brute-force example: 3, 10, 5, 25, 2 and 8. The largest is 25, so five bits are enough to write every number. In five bits they are 00011, 01010, 00101, 11001, 00010 and 01000.

Take x = 25, which is 11001. Its best partner is the stored number whose bits differ from 11001 in the most valuable places. The walk decides one bit at a time, starting at the top. At each bit, the candidates are the stored numbers that still agree with every choice made so far. The table shows the walk.

Work through the first row. The top bit of 25 is 1. The walk wants a 0, and the candidates 3, 10, 5, 2 and 8 all have a 0 at bit 4, so the walk takes that child. The XOR at this bit is 1 XOR 0, which is 1, so the result gets 16.

The second row is where the greedy rule pays off. Bit 3 of 25 is also 1. The walk wants a 0 again, and 3, 5 and 2 have one. It takes them, and the result gets 8 more, so it is now 24. Notice that 10 and 8 are dropped here, because each has a 1 at bit 3 and so cannot give a 1 in the XOR at this bit.

The third row shows the walk switching direction. Bit 2 of 25 is 0, so the walk wants a 1. Among 3, 5 and 2, only 5 has a 1 at bit 2. The walk takes it, and the result gets 4, which makes 28.

After that the candidates are down to 5 alone. Each remaining bit has no opposite left, so the walk follows the same bit as 5 and adds nothing. The answer is 28, the XOR of 25 and 5. The brute force agrees: 25 with 3 gives 26, 25 with 10 gives 19, 25 with 2 gives 27 and 25 with 8 gives 17. None of them is larger than 28.

This is why the greedy rule is safe. The top bit set the 16, the second bit set the 8, and so on. Once a choice was made, the walk never had to revisit it, because a higher bit is worth more than every lower bit put together.

Counting pairs below a limit

A harder question asks for the number of pairs whose XOR is less than a limit L. The brute force again tries every pair, so the trie method is needed for the same reason as before. It stores counts instead of only the paths, and it counts the matches on each bit.

The idea is to process the numbers in order. For each new number x, count how many earlier numbers y give x ^ y < L. Then insert x and move on. Every pair is counted exactly once, when its later number arrives.

To count the earlier y, walk the trie with x, comparing the XOR with L bit by bit from the top. At a bit where L has a 1, a XOR bit of 0 makes the XOR smaller than L at this position, no matter what the lower bits are. So all the earlier numbers that agree with x at this bit are already counted, and you add the count stored on that child. Then you continue down the other child, where the XOR bit is 1, to keep the XOR equal to L so far. At a bit where L has a 0, a XOR bit of 1 would make the XOR larger, so you must continue only on the child that keeps the XOR bit at 0.

Each node keeps a count of the numbers that pass through it. The insert adds 1 to each node on the path. The count lets the walk add a whole group of matches at once, without visiting them.

The program prints:

4
10
0

Check the first line by hand. The pairs are 1 with 2 (XOR 3), 1 with 3 (XOR 2), 2 with 3 (XOR 1), and 4 with 5 (XOR 1). Each of those four is less than 4. The other six pairs give 4, 5, 6, 6, 7 and 7, and none of them is below 4. So the answer is 4. With a limit of 100, every one of the 10 pairs counts, which is the second line. With a limit of 0, no XOR is below 0, so the answer is 0.

In the Java version of this program, the total is a long, because a pair count can grow past the largest 32-bit int. Python integers have no fixed size, so the total grows as needed and never wraps around. You do not declare a type for it. Python still needs the count to be correct, and the walk above is correct for any number of inputs, as long as each value fits in 30 bits.

Also look at the check if node is None: break. A walk can run out of trie when the limit is small, because the remaining branches may hold no numbers. The check stops the walk cleanly instead of reading an attribute of None.

Worked trace: counting pairs for 1 to 5

The counting method is easier to trust after one run by hand. Take the numbers 1, 2, 3, 4 and 5, with a limit of 4. Each row handles one new number. It counts the earlier numbers whose XOR with it is below 4, and then the new number joins the set.

The row for 3 counts two earlier numbers, and both XORs are below the limit. The row for 4 has no pairs below the limit, because every XOR is 5 or more. The row for 5 is the subtle one. The XOR with 1 is 4, which is not below 4, so it is not counted. The XOR with 4 is 1, which is counted. The final total is 4, which matches the program.

The trie does not compare each pair one at a time like this table. At each bit where the limit has a 1, it adds the stored count of a whole group of earlier numbers at once. For the number 5, the limit 4 is 100 in binary. At the top bit, the group that agrees with 5 there is the number 4, and the walk adds its count, which is 1. Then it continues on the other side, where the XORs are too large to count. The table is the slow version of the same count, and it is the right tool for checking a walk by hand before you trust the code.

Queries: the best partner for many numbers

A common variation gives you one fixed set of numbers and then many queries. For each query value x, you want the largest x ^ a over the set. This is the same greedy walk, run once per query. The trie is built once, and each query costs about 31 steps. The program below does this for three queries. The set is 3, 10, 5, 25 and 2, and the queries are 4, 8 and 30.

The program prints:

4 -> 29
8 -> 17
30 -> 29

Check one of them. For the query 8, the partners give 8 ^ 3 = 11, 8 ^ 10 = 2, 8 ^ 5 = 13, 8 ^ 25 = 17 and 8 ^ 2 = 10. The largest is 17, from 25. The query 8 is not in the set, and the walk still works, because the trie does not need x to be stored. It only needs the stored numbers to form a complete path for each bit choice.

What happens inside the computer

A Python int holds as many bits as the value needs, and it has no fixed width. The code uses bits 30 down to 0 by choice. It keeps the trie a fixed depth of 31 levels, so each walk takes the same number of steps. The expression (x >> bit) & 1 shifts x right by bit places, which moves the bit we want into the lowest position, and then keeps only that lowest bit. For x equal to 6, which is 110, the expression at bit 1 gives 110 >> 1 equal to 11, and 11 & 1 equal to 1.

That fixed width is the one limit the Python version must respect. Any bit above position 30 is never looked at. Python will not complain, so the answer can be wrong. The program below shows it. The value 2 to the power 31 needs bit 31, which the trie does not look at. It stores 2^31 and 1, and then asks for the best partner of 1. The correct answer is 2^31 XOR 1, which is 2147483649. The trie gives 1.

The output is:

trie: 1
correct: 2147483649

The fix is to choose the bit width from the data. The largest value in the list tells you how many bits you need, and the method int.bit_length() returns that count. For the value 2^31 it is 32, so the walk must start at bit 31. The design choice is the same in every other language: pick a width that covers every value, and use it for every insert and every walk.

A stored node is a Python object. On the machine used for this lesson, sys.getsizeof reports 48 bytes for a Node object and 72 bytes for its two-slot list, which is 120 bytes per node before counting anything the node points to. A node created by an insert takes that much space. Each insert creates up to 31 new nodes in the worst case. With 100,000 numbers, that is up to 3.1 million nodes, or about 370 MB, which is a lot of memory for a small machine. The real number is smaller, because the top levels are shared by many numbers. Still, the cost is high. A layout that stores the children as plain integers in one large array uses much less space. The array module in the standard library does that, and each slot then holds a 4-byte index into the array, with index 0 meaning "no child". The idea stays the same, and only the storage changes.

Time is O(31 * n) for building and O(31) per query, which is O(n) for a fixed number of bits. Space is the node count, as above.

Common mistakes

Starting from the lowest bit. The greedy choice only works from the highest bit down, because the high bits outweigh the low ones. A walk from bit 0 up would choose the wrong partner and give a wrong answer for many inputs.

Mixing up XOR and the power sign. In Python, ^ is XOR. The expression 2 ^ 3 is 1, not 8. To raise to a power you use **, as in 2 ** 3. The trie code never needs a power except through 1 << bit.

Leaving out high bits. The trie covers bits 30 down to 0. A number with a larger bit set is cut at bit 31 and above, and the walk is wrong without any error. The example above shows this with 2^31. Pick the width from the largest value, using max(nums).bit_length().

Expecting a pair count to overflow. A pair count can be large, but a Python int grows to fit it. The worry about wrap-around, which Java programs have with int and must solve with long, does not apply here. Use the same walk and trust the number.

Forgetting the counts on insert. In the counting method, the count on each node must be updated along the whole path during insert. If you update only the leaf, the walk adds the wrong totals at the higher nodes, and the answer is wrong on inputs that look fine.

Counting a pair twice. The loop processes each number against the earlier ones, so each pair is counted once. If you count against all numbers, including later ones, every pair is counted twice, and the answer is double the right value.

Mixing bit ranges in one trie. The counting program uses bits 29 down to 0, and the max-XOR program uses bits 30 down to 0. Each trie must use one range for every insert and every walk. If inserts use one range and walks use another, the levels do not line up. The walk then either reads None as a node and fails with an AttributeError, or it returns a wrong answer.

Assuming the opposite child exists. The opposite child may be missing. The code must check it, as best_xor_with does. Only the same-bit child is guaranteed when the opposite one is missing, because a node always has at least one child.

Debugging walkthrough: a wrong answer on small input

Suppose the program prints 0 for the numbers 1 and 2. The correct answer is 1 ^ 2 = 3, so something is wrong. Work through the trace by hand before you touch the code.

Insert 1 and 2. The number 1 is 01 and the number 2 is 10, so their paths split at bit 1. Now run the walk for x = 1, starting at the top of the trie. For the high bits, x has 0 and so does every stored number, so the walk moves down the 0 children and sets nothing. At bit 1, x has 0, so the opposite is 1, and the 1 child exists because of the number 2. So the walk should set bit 1 of the result and go down that child. At bit 0, x has 1, so the opposite is 0, and the number 2 has 0 there, so the walk should set bit 0 as well. The result should be 11, which is 3.

Since the output is 0, neither bit was set. That points at the line result |= 1 << bit. Check that it is in the if branch, that it runs for the right bit, and that it is not reset later. A bug in the insert, such as creating the wrong child, would also produce 0, so check the insert path for 2 as well.

That kind of trace, done on paper with two or three numbers, finds nearly every bug in this lesson. Use it before you read the code again.

Variations and edge cases

One number. With only one number, the largest XOR of two numbers does not exist. The brute force returns 0 for a list with fewer than two numbers, which is the sensible default.

Equal numbers. Two equal numbers XOR to 0. A list of equal numbers has a largest XOR of 0, and the trie walk gives that too.

Zero. The number 0 has all bits 0, so its walk always wants 1 bits. It finds the number with the most differing bits. Zero is a normal input.

The limit zero. Pairs with XOR below 0 do not exist, so the count is 0. The walk adds nothing because no limit bit is set.

Large values near the top. Values up to 10^9 fit under 2^30, which is why bits 29 down to 0 are enough for the counting method. The query method uses bits 30 down to 0, which covers every value up to 2,147,483,647. Larger values need a wider walk, as the example with 2^31 showed.

Negative numbers. Python's >> and & work on negative numbers too, as if they had infinitely many 1 bits on the left. A trie of fixed width does not model that, so a negative value gives an answer that depends on its low bits only. The problems in this lesson use non-negative numbers, and the code assumes them.

Other uses. The maximum XOR subarray uses prefix XORs, which are the same idea as prefix sums: the XOR of a subarray equals the XOR of two prefixes. So the same trie answers the question for subarrays too. Counting pairs with a limit appears in many contest problems.

Interview-style questions and real uses

The usual question is "find the maximum XOR of two numbers in a list." The answer to give is the brute force first, then the trie. Explain why the trie is correct: the highest differing bit decides the answer, and the greedy walk makes that choice at each level. Then give the complexity: O(31 * n), which is linear for a fixed number of bits.

A good follow-up is "what if the numbers come in a stream?" The trie handles that naturally, because you insert each new number as it arrives and query against the ones before it.

Another follow-up is "what if you need the actual pair, not only the value?" Store the index or the value at the leaf. Then the walk can return the number it ended on, which is the partner.

Real systems use a binary trie of the same shape. Network routers need to decide which route a packet should follow, using the longest matching prefix of its destination address. Each address is a sequence of bits, and the routing table is a trie over those bits. The walk follows the bits of the address and remembers the last route it passed. That is the same walk you have just written, with a different stopping rule.

More uses for the same walk

Two more uses are worth knowing for interviews. The first is the maximum XOR of a subarray. A prefix XOR is the XOR of all the numbers from the start of the list up to some point. The XOR of any subarray equals the XOR of two prefix XORs, because the shared part cancels out. So the largest subarray XOR is the largest XOR of two prefix values, and the trie answers that question in linear time.

The second is a nearest-match question. Given a stored set and a query, which stored number agrees with the query in the most leading bits? That is the same walk, except that the choice at each bit follows the matching bit instead of the opposite one. Say that in an interview, and point out that the walk is the one from this lesson with a different rule for the choice.

Practice

1. Compute 6 ^ 3 by hand in binary. Hint: write 6 as 110 and 3 as 011, and apply the table column by column.

Show the answer: 110 XOR 011 gives 101, which is 4 + 1 = 5. So 6 ^ 3 is 5.

2. For the numbers [8, 1], what does the max-XOR program print? Explain using their binary forms.

Show the answer: It prints 9. Eight is 1000 and 1 is 0001. Their XOR is 1001, which is 8 + 1 = 9. The only pair is 8 and 1, so the answer is their XOR. The walk from 1 wants a 1 at bit 3, and 8 has one there. At bit 0 it wants a 0, and 8 has a 0 there too.

3. Why does a 1 at a high bit beat any combination of lower bits?

Show the answer: A bit at position k is worth 2 to the power k. The highest possible total from all the lower bits is 2 to the power k, minus 1. So one bit at position k always adds more than the whole lower part can add together.

4. Run the greedy max-XOR walk by hand for x = 2 on the trie of 1, 2 and 5. Say which children it takes at each bit.

Show the answer: At bit 2, x has 0, so it takes the child for 1. At bit 1, x has 1, so it takes the child for 0. At bit 0, x has 0, so it takes the child for 1. The path is 1, 10, 101, which is the number 5, and the XOR is 7.

5. Change the counting program so that it counts pairs with XOR at least L, instead of less than L. Which line changes, and why?

Show the answer: Each new number has i earlier numbers, where i is its position in the list, counting from 0. The pairs at least L are the earlier numbers minus the pairs below L. So in count_pairs, add i - count_below(root, x, limit) instead of count_below(root, x, limit), with i taken from enumerate(nums). The walk itself does not change.

6. A version of the counting program checks each number against all the others, both earlier and later, and does not divide the total by 2. For the numbers [1, 2, 3, 4, 5] with limit 4, what does it print?

Show the answer: It prints 8. Each of the four pairs with XOR below 4 is counted twice, once from each end, so the total is 2 times 4. The fix is to count only against earlier numbers, as the program in this lesson does.

7. Explain why a Python count of pairs cannot overflow, and give the number of pairs for n equal to 100,000.

Show the answer: The number of pairs is n * (n - 1) / 2. For n equal to 100,000, that is 4,999,950,000. A Java int cannot hold that, and it would wrap around. A Python int grows to hold any size, so the total is printed correctly without any type declaration.

8. Why does the greedy walk not need to check whether x is itself in the trie?

Show the answer: The walk compares x with every stored number through the bits, so it finds the best partner whether or not x is stored. If x is stored, the best partner might be x itself, which gives XOR 0. That is harmless, because the answer is the largest XOR and 0 is never larger than a real pair.

9. Why does the trie use bits 30 down to 0, and what would change if you used 31 instead? What would change if the numbers could be as large as 2^40?

Show the answer: Bits 30 to 0 cover every whole number up to 2,147,483,647. Starting at bit 31 adds one level to every walk. For ordinary inputs that bit is always 0, so the level costs time and changes no result. For values as large as 2^40, the walk must start at bit 40, which is one less than the bit_length of the largest value. Otherwise bit 40 is ignored, and the answer is wrong without any error.

10. Give the running time of the max-XOR program for n numbers, and say what it means that the time is linear.

Show the answer: It is O(31 * n), which simplifies to O(n) because 31 is a fixed number. Linear means the time doubles when n doubles, which is far better than the n squared growth of the brute force.

What you now know

• A number is a row of bits, and XOR gives 1 where bits differ.
• The highest bit that differs decides the size of a XOR, so the greedy walk picks the opposite bit at each level.
• A binary trie stores the bits of each number, two children per node, from bit 30 down to bit 0.
• The max-XOR walk takes about 31 steps per number, which is linear in n for a fixed bit width.
• Counting pairs below a limit adds, at each limit bit, the count of a whole group of earlier numbers.
• The bit width must cover the largest value, because Python will not warn you about bits the trie never reads. Check that the opposite child exists before you move into it.

In the module assignment you will combine these ideas. You will build a small word store that adds, removes and suggests words, and you will test it against your own checks.