TRIE-5 Bitwise tries for XOR · DSA

A trie works on any sequence of symbols, and a number written in binary is a sequence of 0s and 1s. A trie of numbers, read from the highest bit down, answers questions about XOR that would otherwise need every pair of numbers.

Numbers as words of bits

In binary, every digit is a bit, 0 or 1, and the digits are worth 1, 2, 4, 8, … from the right: the bit in place k (counting from 0 on the right) is worth 2^k, that is, k twos multiplied together (and 2⁰ is 1). So 1010 is 8 + 2 = 10. In Python, bin(10) gives '0b1010', and x >> k & 1 reads bit k of x: >> k shifts the bits k places to the right, and & 1 keeps only the last one.

XOR (“exclusive or”, written ^ in Python) combines two numbers bit by bit: a result bit is 1 when the two bits differ, and 0 when they are the same. So 0011 ^ 1001 = 1010, that is, 3 XOR 9 = 10. Two facts are used often: x ^ x = 0, and x ^ 0 = x.

To store numbers in a trie, write them all with the same number of bits, B, highest bit first. Each number becomes a word of exactly B letters over the alphabet 0 and 1, and every leaf is on the bottom level. Numbers below about a billion fit in 30 bits, since 2³⁰ = 1,073,741,824.

The best partner, bit by bit

The question: given a number x, which stored number y makes x ^ y as large as possible? Trying every y costs O(n). The trie does it in B steps. Walk down from the root. At each level, look at x’s bit, and take the edge with the opposite bit if it exists, because that makes this result bit 1. If it does not exist, take the other edge, and this result bit is 0.

FIG TRIE-5.1A trie of bits and the largest XOR

Job

numbers

1/7

Write each number with the same number of bits, 4 here, highest bit first. Each number is then a 4-letter word over the letters 0 and 1.

Step 1 of 7

Why is it right to grab a 1 in the highest place, even if it leads to 0s everywhere below? Because one bit outweighs all the bits below it:

So any number with a 1 in place k beats any number with a 0 there, if they agree in the higher places. The walk fixes the result one bit at a time, from the top, and each choice is the best possible given the bits above it. A choice that looks good now and is never wrong later is called a greedy choice; GRDY studies when such choices are safe.

The largest XOR of any two stored numbers is then the largest best-partner result over all the numbers (the third variant). It is enough to compare each number with the numbers inserted before it: insert the numbers one by one, and before inserting x, find its best partner among those already stored.

The code and its cost

B = 30  # numbers below 2**30

def max_xor(nums):
    root = [None, None]          # a node: [child for 0, child for 1]
    best = 0
    for i, x in enumerate(nums):
        if i > 0:                # best partner among earlier numbers
            node, r = root, 0
            for k in range(B - 1, -1, -1):
                b = x >> k & 1
                if node[1 - b] is not None:   # the opposite bit
                    r |= 1 << k               # this result bit is 1
                    node = node[1 - b]
                else:
                    node = node[b]
            best = max(best, r)
        node = root              # insert x
        for k in range(B - 1, -1, -1):
            b = x >> k & 1
            if node[b] is None:
                node[b] = [None, None]
            node = node[b]
    return best

A node with only two possible children can be a list of two items instead of a dict, which is smaller and faster. 1 << k is 2^k, and r |= 1 << k sets bit k of r to 1 (| is bitwise “or”).

Each number costs one walk down and one insert, 2B steps, so the total is O(n · B) time and at most n · B nodes. For 100,000 numbers of 30 bits that is about 6 million steps, against about 5 billion pairs for the direct method. Practice TRIE-P5 asks for this.

Bitwise tries for XOR

Numbers as words of bits

The best partner, bit by bit

The code and its cost

Other questions it answers