Skip to main content
CodePeet

CodePeet 700 Complete DSA Sheet

Bitwise Tries: Maximum XOR

Editorial

Every pair is its own question

Maximum XOR of Two Numbers in an Array asks for the largest a XOR b over any two numbers of a list. The solution everyone writes first tries every pair. Here it is against a trie of the numbers' bits, on 5,000 numbers of 30 bits, the same in every language:

import time

x = 3                                         # the same numbers in every language


def next_number():
    global x
    x = x * 48271 % 2147483647
    return x


B = 30
nums = [next_number() % (1 << B) for _ in range(5000)]
print(len(nums), "numbers of", B, "bits")

start = time.perf_counter()
best_pairs, tried = 0, 0
for i in range(len(nums)):                    # every pair: n(n - 1) / 2 XORs
    a = nums[i]
    for j in range(i + 1, len(nums)):
        if a ^ nums[j] > best_pairs:
            best_pairs = a ^ nums[j]
    tried += len(nums) - i - 1
pairs_ms = round((time.perf_counter() - start) * 1000)

start = time.perf_counter()
zero, one = [0], [0]                          # node k's children; 0 means none, since no node's child is the root
steps = 0


def insert(v):
    global steps
    node = 0
    for b in range(B - 1, -1, -1):            # the highest bit first
        steps += 1
        side = one if (v >> b) & 1 else zero
        if side[node] == 0:
            zero.append(0)
            one.append(0)
            side[node] = len(zero) - 1
        node = side[node]


def best_with(v):                             # the largest v ^ y over the numbers in the trie
    global steps
    node, xor = 0, 0
    for b in range(B - 1, -1, -1):
        steps += 1
        bit = (v >> b) & 1
        other = zero if bit else one          # the child for the opposite bit
        if other[node]:
            xor |= 1 << b
            node = other[node]
        else:
            node = (one if bit else zero)[node]
    return xor


best_trie = 0
for k, v in enumerate(nums):
    if k:
        best_trie = max(best_trie, best_with(v))   # against every number before it
    insert(v)
trie_ms = round((time.perf_counter() - start) * 1000)

print("largest XOR:", best_pairs, "from every pair,", best_trie, "with the bit trie")
print("work:", tried, "XORs for every pair,", steps, "steps in the bit trie")
print(f"time: {pairs_ms} ms for every pair, {trie_ms} ms with the bit trie")

# 5000 numbers of 30 bits
# largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
# work: 12497500 XORs for every pair, 299970 steps in the bit trie
# time: 1507 ms for every pair, 64 ms with the bit trie
public class Main {
    static long x = 3;                               // the same numbers in every language
    static final int B = 30;
    static int[] zero, one;                          // node k's children; 0 means none, since no node's child is the root
    static int size = 1;
    static long steps = 0;

    static int nextNumber() {
        x = x * 48271 % 2147483647;
        return (int) x;
    }

    static void insert(int v) {
        int node = 0;
        for (int b = B - 1; b >= 0; b--) {           // the highest bit first
            steps++;
            int[] side = ((v >> b) & 1) == 1 ? one : zero;
            if (side[node] == 0) side[node] = size++;
            node = side[node];
        }
    }

    static int bestWith(int v) {                     // the largest v ^ y over the numbers in the trie
        int node = 0, xor = 0;
        for (int b = B - 1; b >= 0; b--) {
            steps++;
            int bit = (v >> b) & 1;
            int[] other = bit == 1 ? zero : one;     // the child for the opposite bit
            if (other[node] != 0) {
                xor |= 1 << b;
                node = other[node];
            } else {
                node = (bit == 1 ? one : zero)[node];
            }
        }
        return xor;
    }

    public static void main(String[] args) {
        int n = 5000;
        int[] nums = new int[n];
        for (int k = 0; k < n; k++) nums[k] = nextNumber() % (1 << B);
        System.out.println(n + " numbers of " + B + " bits");

        long start = System.nanoTime();
        int bestPairs = 0;
        long tried = 0;
        for (int i = 0; i < n; i++) {                // every pair: n(n - 1) / 2 XORs
            int a = nums[i];
            for (int j = i + 1; j < n; j++)
                if ((a ^ nums[j]) > bestPairs) bestPairs = a ^ nums[j];
            tried += n - i - 1;
        }
        long pairsMs = (System.nanoTime() - start) / 1000000;

        start = System.nanoTime();
        zero = new int[n * B + 1];
        one = new int[n * B + 1];
        int bestTrie = 0;
        for (int k = 0; k < n; k++) {
            if (k > 0) bestTrie = Math.max(bestTrie, bestWith(nums[k]));   // against every number before it
            insert(nums[k]);
        }
        long trieMs = (System.nanoTime() - start) / 1000000;

        System.out.println("largest XOR: " + bestPairs + " from every pair, " + bestTrie + " with the bit trie");
        System.out.println("work: " + tried + " XORs for every pair, " + steps + " steps in the bit trie");
        System.out.println("time: " + pairsMs + " ms for every pair, " + trieMs + " ms with the bit trie");
    }
}

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 46 ms for every pair, 8 ms with the bit trie
#include <bits/stdc++.h>
using namespace std;

long long x = 3;                              // the same numbers in every language
const int B = 30;
vector<int> zero, one;                        // node k's children; 0 means none, since no node's child is the root
long long steps = 0;

int next_number() {
    x = x * 48271 % 2147483647;
    return (int) x;
}

void insert(int v) {
    int node = 0;
    for (int b = B - 1; b >= 0; b--) {        // the highest bit first
        steps++;
        vector<int>& side = ((v >> b) & 1) ? one : zero;
        if (side[node] == 0) {
            zero.push_back(0);
            one.push_back(0);
            side[node] = (int) zero.size() - 1;
        }
        node = side[node];
    }
}

int bestWith(int v) {                         // the largest v ^ y over the numbers in the trie
    int node = 0, xr = 0;
    for (int b = B - 1; b >= 0; b--) {
        steps++;
        int bit = (v >> b) & 1;
        vector<int>& other = bit ? zero : one;   // the child for the opposite bit
        if (other[node]) {
            xr |= 1 << b;
            node = other[node];
        } else {
            node = (bit ? one : zero)[node];
        }
    }
    return xr;
}

int main() {
    int n = 5000;
    vector<int> nums(n);
    for (int k = 0; k < n; k++) nums[k] = next_number() % (1 << B);
    cout << n << " numbers of " << B << " bits\n";

    auto start = chrono::steady_clock::now();
    int bestPairs = 0;
    long long tried = 0;
    for (int i = 0; i < n; i++) {             // every pair: n(n - 1) / 2 XORs
        int a = nums[i];
        for (int j = i + 1; j < n; j++)
            if ((a ^ nums[j]) > bestPairs) bestPairs = a ^ nums[j];
        tried += n - i - 1;
    }
    long long pairsMs = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();

    start = chrono::steady_clock::now();
    zero.assign(1, 0);
    one.assign(1, 0);
    zero.reserve(n * B + 1);
    one.reserve(n * B + 1);
    int bestTrie = 0;
    for (int k = 0; k < n; k++) {
        if (k > 0) bestTrie = max(bestTrie, bestWith(nums[k]));   // against every number before it
        insert(nums[k]);
    }
    long long trieMs = chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - start).count();

    cout << "largest XOR: " << bestPairs << " from every pair, " << bestTrie << " with the bit trie\n";
    cout << "work: " << tried << " XORs for every pair, " << steps << " steps in the bit trie\n";
    cout << "time: " << pairsMs << " ms for every pair, " << trieMs << " ms with the bit trie\n";
}

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 2 ms for every pair, 1 ms with the bit trie
let x = 3;                                    // the same numbers in every language

function nextNumber() {
    x = x * 48271 % 2147483647;
    return x;
}

const B = 30;
const n = 5000;
const nums = [];
for (let k = 0; k < n; k++) nums.push(nextNumber() % (1 << B));
console.log(`${n} numbers of ${B} bits`);

let start = performance.now();
let bestPairs = 0, tried = 0;
for (let i = 0; i < n; i++) {                 // every pair: n(n - 1) / 2 XORs
    const a = nums[i];
    for (let j = i + 1; j < n; j++)
        if ((a ^ nums[j]) > bestPairs) bestPairs = a ^ nums[j];
    tried += n - i - 1;
}
const pairsMs = Math.round(performance.now() - start);

start = performance.now();
const zero = new Int32Array(n * B + 1);       // node k's children; 0 means none, since no node's child is the root
const one = new Int32Array(n * B + 1);
let size = 1, steps = 0;

function insert(v) {
    let node = 0;
    for (let b = B - 1; b >= 0; b--) {        // the highest bit first
        steps++;
        const side = (v >> b) & 1 ? one : zero;
        if (side[node] === 0) side[node] = size++;
        node = side[node];
    }
}

function bestWith(v) {                        // the largest v ^ y over the numbers in the trie
    let node = 0, xor = 0;
    for (let b = B - 1; b >= 0; b--) {
        steps++;
        const bit = (v >> b) & 1;
        const other = bit ? zero : one;       // the child for the opposite bit
        if (other[node] !== 0) {
            xor |= 1 << b;
            node = other[node];
        } else {
            node = (bit ? one : zero)[node];
        }
    }
    return xor;
}

let bestTrie = 0;
for (let k = 0; k < n; k++) {
    if (k > 0) bestTrie = Math.max(bestTrie, bestWith(nums[k]));   // against every number before it
    insert(nums[k]);
}
const trieMs = Math.round(performance.now() - start);

console.log(`largest XOR: ${bestPairs} from every pair, ${bestTrie} with the bit trie`);
console.log(`work: ${tried} XORs for every pair, ${steps} steps in the bit trie`);
console.log(`time: ${pairsMs} ms for every pair, ${trieMs} ms with the bit trie`);

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 24 ms for every pair, 9 ms with the bit trie
let x = 3;                                    // the same numbers in every language

function nextNumber(): number {
    x = x * 48271 % 2147483647;
    return x;
}

const B = 30;
const n = 5000;
const nums: number[] = [];
for (let k = 0; k < n; k++) nums.push(nextNumber() % (1 << B));
console.log(`${n} numbers of ${B} bits`);

let start = performance.now();
let bestPairs = 0, tried = 0;
for (let i = 0; i < n; i++) {                 // every pair: n(n - 1) / 2 XORs
    const a = nums[i];
    for (let j = i + 1; j < n; j++)
        if ((a ^ nums[j]) > bestPairs) bestPairs = a ^ nums[j];
    tried += n - i - 1;
}
const pairsMs = Math.round(performance.now() - start);

start = performance.now();
const zero = new Int32Array(n * B + 1);       // node k's children; 0 means none, since no node's child is the root
const one = new Int32Array(n * B + 1);
let size = 1, steps = 0;

function insert(v: number): void {
    let node = 0;
    for (let b = B - 1; b >= 0; b--) {        // the highest bit first
        steps++;
        const side = (v >> b) & 1 ? one : zero;
        if (side[node] === 0) side[node] = size++;
        node = side[node];
    }
}

function bestWith(v: number): number {        // the largest v ^ y over the numbers in the trie
    let node = 0, xor = 0;
    for (let b = B - 1; b >= 0; b--) {
        steps++;
        const bit = (v >> b) & 1;
        const other = bit ? zero : one;       // the child for the opposite bit
        if (other[node] !== 0) {
            xor |= 1 << b;
            node = other[node];
        } else {
            node = (bit ? one : zero)[node];
        }
    }
    return xor;
}

let bestTrie = 0;
for (let k = 0; k < n; k++) {
    if (k > 0) bestTrie = Math.max(bestTrie, bestWith(nums[k]));   // against every number before it
    insert(nums[k]);
}
const trieMs = Math.round(performance.now() - start);

console.log(`largest XOR: ${bestPairs} from every pair, ${bestTrie} with the bit trie`);
console.log(`work: ${tried} XORs for every pair, ${steps} steps in the bit trie`);
console.log(`time: ${pairsMs} ms for every pair, ${trieMs} ms with the bit trie`);

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 25 ms for every pair, 9 ms with the bit trie
using System;
using System.Diagnostics;

class Program {
    static long x = 3;                        // the same numbers in every language
    const int B = 30;
    static int[] zero, one;                   // node k's children; 0 means none, since no node's child is the root
    static int size = 1;
    static long steps = 0;

    static int NextNumber() {
        x = x * 48271 % 2147483647;
        return (int) x;
    }

    static void Insert(int v) {
        int node = 0;
        for (int b = B - 1; b >= 0; b--) {    // the highest bit first
            steps++;
            int[] side = ((v >> b) & 1) == 1 ? one : zero;
            if (side[node] == 0) side[node] = size++;
            node = side[node];
        }
    }

    static int BestWith(int v) {              // the largest v ^ y over the numbers in the trie
        int node = 0, xor = 0;
        for (int b = B - 1; b >= 0; b--) {
            steps++;
            int bit = (v >> b) & 1;
            int[] other = bit == 1 ? zero : one;   // the child for the opposite bit
            if (other[node] != 0) {
                xor |= 1 << b;
                node = other[node];
            } else {
                node = (bit == 1 ? one : zero)[node];
            }
        }
        return xor;
    }

    static void Main() {
        int n = 5000;
        var nums = new int[n];
        for (int k = 0; k < n; k++) nums[k] = NextNumber() % (1 << B);
        Console.WriteLine($"{n} numbers of {B} bits");

        var watch = Stopwatch.StartNew();
        int bestPairs = 0;
        long tried = 0;
        for (int i = 0; i < n; i++) {         // every pair: n(n - 1) / 2 XORs
            int a = nums[i];
            for (int j = i + 1; j < n; j++)
                if ((a ^ nums[j]) > bestPairs) bestPairs = a ^ nums[j];
            tried += n - i - 1;
        }
        long pairsMs = watch.ElapsedMilliseconds;

        watch.Restart();
        zero = new int[n * B + 1];
        one = new int[n * B + 1];
        int bestTrie = 0;
        for (int k = 0; k < n; k++) {
            if (k > 0) bestTrie = Math.Max(bestTrie, BestWith(nums[k]));   // against every number before it
            Insert(nums[k]);
        }
        long trieMs = watch.ElapsedMilliseconds;

        Console.WriteLine($"largest XOR: {bestPairs} from every pair, {bestTrie} with the bit trie");
        Console.WriteLine($"work: {tried} XORs for every pair, {steps} steps in the bit trie");
        Console.WriteLine($"time: {pairsMs} ms for every pair, {trieMs} ms with the bit trie");
    }
}

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 8 ms for every pair, 3 ms with the bit trie
package main

import (
	"fmt"
	"time"
)

var x int64 = 3 // the same numbers in every language

const B = 30

var zero, one []int32 // node k's children; 0 means none, since no node's child is the root
var size int32 = 1
var steps int64

func nextNumber() int {
	x = x * 48271 % 2147483647
	return int(x)
}

func insert(v int) {
	node := int32(0)
	for b := B - 1; b >= 0; b-- { // the highest bit first
		steps++
		side := zero
		if (v>>b)&1 == 1 {
			side = one
		}
		if side[node] == 0 {
			side[node] = size
			size++
		}
		node = side[node]
	}
}

func bestWith(v int) int { // the largest v ^ y over the numbers in the trie
	node, xor := int32(0), 0
	for b := B - 1; b >= 0; b-- {
		steps++
		bit := (v >> b) & 1
		same, other := zero, one // the child for the same bit, and for the opposite bit
		if bit == 1 {
			same, other = one, zero
		}
		if other[node] != 0 {
			xor |= 1 << b
			node = other[node]
		} else {
			node = same[node]
		}
	}
	return xor
}

func main() {
	n := 5000
	nums := make([]int, n)
	for k := range nums {
		nums[k] = nextNumber() % (1 << B)
	}
	fmt.Printf("%d numbers of %d bits\n", n, B)

	start := time.Now()
	bestPairs, tried := 0, int64(0)
	for i := 0; i < n; i++ { // every pair: n(n - 1) / 2 XORs
		a := nums[i]
		for j := i + 1; j < n; j++ {
			if a^nums[j] > bestPairs {
				bestPairs = a ^ nums[j]
			}
		}
		tried += int64(n - i - 1)
	}
	pairsMs := time.Since(start).Milliseconds()

	start = time.Now()
	zero = make([]int32, n*B+1)
	one = make([]int32, n*B+1)
	bestTrie := 0
	for k, v := range nums {
		if k > 0 {
			if got := bestWith(v); got > bestTrie { // against every number before it
				bestTrie = got
			}
		}
		insert(v)
	}
	trieMs := time.Since(start).Milliseconds()

	fmt.Printf("largest XOR: %d from every pair, %d with the bit trie\n", bestPairs, bestTrie)
	fmt.Printf("work: %d XORs for every pair, %d steps in the bit trie\n", tried, steps)
	fmt.Printf("time: %d ms for every pair, %d ms with the bit trie\n", pairsMs, trieMs)
}

// 5000 numbers of 30 bits
// largest XOR: 1073741822 from every pair, 1073741822 with the bit trie
// work: 12497500 XORs for every pair, 299970 steps in the bit trie
// time: 8 ms for every pair, 2 ms with the bit trie

Both found the same largest XOR, 1,073,741,822, in all seven languages. Every pair is 12,497,500 XORs; the bit trie took 299,970 steps, 30 to insert each number and 30 to ask with it: 42 times less work. In time that was 1,507 ms against 64 ms in Python. Compiled languages run the pairs fast at this size, 2 ms against 1 ms in C++, but the trie took less in every language, and the pairs grow with the square of the list: twice the numbers is four times the pairs, and only twice the trie's steps.

The pairs ask each number about every other one. The trie asks one question per bit instead: is there a number whose bit here is the opposite of mine?

The trie of 12, 5, 26, 18 and 9 as 5-bit numbers, 01100, 00101, 11010, 10010 and 01001, from the highest bit at the top, a 0 child to the left and a 1 child to the right, each number at the bottom of its path. Beside it, level by level, the bits of 5, the bits the walk takes and their XOR. 1, the walk for 5, 00101, wants the opposite of each bit: 1, 1, 0, 1, 0; 2, every one is there, so the walk takes the path of 26, 11010; 3, 5 XOR 26 is 11111, 31, the largest possible in 5 bits. Focal line: take the opposite bit whenever it's there. Title: a trie of bits.

A trie of bits

A number is a word of bits. Pick a width B, enough for the largest number (30 bits here, 31 for any non-negative 32-bit integer), and insert each number's bits from the highest to the lowest, padding small numbers with 0s on the left. Every node then has at most two children, one for a 0 bit and one for a 1, and every number is a path of exactly B steps.

To find the number y in the trie with the largest v XOR y, walk v's bits from the highest and take the child for the opposite bit whenever it exists. An opposite bit puts a 1 in that place of the XOR. Where the opposite child is missing, take the same bit, and that place of the XOR is 0. Here it is on five numbers of 5 bits:

B = 5                                         # every number here is below 2^5 = 32


class Node:
    def __init__(self):
        self.children = [None, None]          # the 0 child and the 1 child
        self.number = None                    # at the bottom: the number these bits spell


def insert(root, v):
    node = root
    for b in range(B - 1, -1, -1):            # the highest bit first
        bit = (v >> b) & 1
        if node.children[bit] is None:
            node.children[bit] = Node()
        node = node.children[bit]
    node.number = v


def best_partner(root, v):                    # the number y in the trie with the largest v ^ y
    node = root
    for b in range(B - 1, -1, -1):
        bit = (v >> b) & 1
        if node.children[1 - bit] is not None:   # the opposite bit is there: take it
            node = node.children[1 - bit]
        else:
            node = node.children[bit]
    return node.number


nums = [12, 5, 26, 18, 9]
root = Node()
for v in nums:
    insert(root, v)
print("numbers:", ", ".join(f"{v} ({v:05b})" for v in nums))
largest = 0
for v in nums:
    y = best_partner(root, v)
    largest = max(largest, v ^ y)
    print(f"{v}: best partner {y}, XOR {v ^ y} = {v ^ y:05b}")
print("the largest XOR:", largest)

# numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
# 12: best partner 18, XOR 30 = 11110
# 5: best partner 26, XOR 31 = 11111
# 26: best partner 5, XOR 31 = 11111
# 18: best partner 12, XOR 30 = 11110
# 9: best partner 18, XOR 27 = 11011
# the largest XOR: 31
import java.util.*;

public class Main {
    static final int B = 5;                          // every number here is below 2^5 = 32

    static class Node {
        final Node[] children = new Node[2];         // the 0 child and the 1 child
        int number;                                  // at the bottom: the number these bits spell
    }

    static String bits(int v) {
        return String.format("%" + B + "s", Integer.toBinaryString(v)).replace(' ', '0');
    }

    static void insert(Node root, int v) {
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {           // the highest bit first
            int bit = (v >> b) & 1;
            if (node.children[bit] == null) node.children[bit] = new Node();
            node = node.children[bit];
        }
        node.number = v;
    }

    static int bestPartner(Node root, int v) {       // the number y in the trie with the largest v ^ y
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (node.children[1 - bit] != null) node = node.children[1 - bit];   // the opposite bit is there: take it
            else node = node.children[bit];
        }
        return node.number;
    }

    public static void main(String[] args) {
        int[] nums = {12, 5, 26, 18, 9};
        Node root = new Node();
        for (int v : nums) insert(root, v);
        StringJoiner line = new StringJoiner(", ");
        for (int v : nums) line.add(v + " (" + bits(v) + ")");
        System.out.println("numbers: " + line);
        int largest = 0;
        for (int v : nums) {
            int y = bestPartner(root, v);
            largest = Math.max(largest, v ^ y);
            System.out.println(v + ": best partner " + y + ", XOR " + (v ^ y) + " = " + bits(v ^ y));
        }
        System.out.println("the largest XOR: " + largest);
    }
}

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31
#include <bits/stdc++.h>
using namespace std;

const int B = 5;                              // every number here is below 2^5 = 32

struct Node {
    Node* children[2] = {};                   // the 0 child and the 1 child
    int number = 0;                           // at the bottom: the number these bits spell
};

string bits(int v) {
    return bitset<B>(v).to_string();
}

void insert(Node* root, int v) {
    Node* node = root;
    for (int b = B - 1; b >= 0; b--) {        // the highest bit first
        int bit = (v >> b) & 1;
        if (!node->children[bit]) node->children[bit] = new Node();
        node = node->children[bit];
    }
    node->number = v;
}

int bestPartner(Node* root, int v) {          // the number y in the trie with the largest v ^ y
    Node* node = root;
    for (int b = B - 1; b >= 0; b--) {
        int bit = (v >> b) & 1;
        if (node->children[1 - bit]) node = node->children[1 - bit];   // the opposite bit is there: take it
        else node = node->children[bit];
    }
    return node->number;
}

int main() {
    vector<int> nums = {12, 5, 26, 18, 9};
    Node* root = new Node();
    for (int v : nums) insert(root, v);
    cout << "numbers: ";
    for (size_t i = 0; i < nums.size(); i++) cout << (i ? ", " : "") << nums[i] << " (" << bits(nums[i]) << ")";
    cout << "\n";
    int largest = 0;
    for (int v : nums) {
        int y = bestPartner(root, v);
        largest = max(largest, v ^ y);
        cout << v << ": best partner " << y << ", XOR " << (v ^ y) << " = " << bits(v ^ y) << "\n";
    }
    cout << "the largest XOR: " << largest << "\n";
}

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31
const B = 5;                                  // every number here is below 2^5 = 32

class Node {
    constructor() {
        this.children = [null, null];         // the 0 child and the 1 child
        this.number = null;                   // at the bottom: the number these bits spell
    }
}

const bits = (v) => v.toString(2).padStart(B, "0");

function insert(root, v) {
    let node = root;
    for (let b = B - 1; b >= 0; b--) {        // the highest bit first
        const bit = (v >> b) & 1;
        if (node.children[bit] === null) node.children[bit] = new Node();
        node = node.children[bit];
    }
    node.number = v;
}

function bestPartner(root, v) {               // the number y in the trie with the largest v ^ y
    let node = root;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (v >> b) & 1;
        if (node.children[1 - bit] !== null) node = node.children[1 - bit];   // the opposite bit is there: take it
        else node = node.children[bit];
    }
    return node.number;
}

const nums = [12, 5, 26, 18, 9];
const root = new Node();
for (const v of nums) insert(root, v);
console.log("numbers:", nums.map((v) => `${v} (${bits(v)})`).join(", "));
let largest = 0;
for (const v of nums) {
    const y = bestPartner(root, v);
    largest = Math.max(largest, v ^ y);
    console.log(`${v}: best partner ${y}, XOR ${v ^ y} = ${bits(v ^ y)}`);
}
console.log("the largest XOR:", largest);

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31
const B = 5;                                  // every number here is below 2^5 = 32

class BitNode {
    children: (BitNode | null)[] = [null, null];   // the 0 child and the 1 child
    number = 0;                               // at the bottom: the number these bits spell
}

const bits = (v: number): string => v.toString(2).padStart(B, "0");

function insert(root: BitNode, v: number): void {
    let node = root;
    for (let b = B - 1; b >= 0; b--) {        // the highest bit first
        const bit = (v >> b) & 1;
        if (node.children[bit] === null) node.children[bit] = new BitNode();
        node = node.children[bit]!;
    }
    node.number = v;
}

function bestPartner(root: BitNode, v: number): number {   // the number y in the trie with the largest v ^ y
    let node = root;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (v >> b) & 1;
        if (node.children[1 - bit] !== null) node = node.children[1 - bit]!;   // the opposite bit is there: take it
        else node = node.children[bit]!;
    }
    return node.number;
}

const nums = [12, 5, 26, 18, 9];
const root = new BitNode();
for (const v of nums) insert(root, v);
console.log("numbers:", nums.map((v) => `${v} (${bits(v)})`).join(", "));
let largest = 0;
for (const v of nums) {
    const y = bestPartner(root, v);
    largest = Math.max(largest, v ^ y);
    console.log(`${v}: best partner ${y}, XOR ${v ^ y} = ${bits(v ^ y)}`);
}
console.log("the largest XOR:", largest);

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31
using System;
using System.Linq;

class Node {
    public readonly Node[] Children = new Node[2];   // the 0 child and the 1 child
    public int Number;                        // at the bottom: the number these bits spell
}

class Program {
    const int B = 5;                          // every number here is below 2^5 = 32

    static string Bits(int v) => Convert.ToString(v, 2).PadLeft(B, '0');

    static void Insert(Node root, int v) {
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {    // the highest bit first
            int bit = (v >> b) & 1;
            if (node.Children[bit] == null) node.Children[bit] = new Node();
            node = node.Children[bit];
        }
        node.Number = v;
    }

    static int BestPartner(Node root, int v) {   // the number y in the trie with the largest v ^ y
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (node.Children[1 - bit] != null) node = node.Children[1 - bit];   // the opposite bit is there: take it
            else node = node.Children[bit];
        }
        return node.Number;
    }

    static void Main() {
        int[] nums = {12, 5, 26, 18, 9};
        var root = new Node();
        foreach (int v in nums) Insert(root, v);
        Console.WriteLine("numbers: " + string.Join(", ", nums.Select(v => $"{v} ({Bits(v)})")));
        int largest = 0;
        foreach (int v in nums) {
            int y = BestPartner(root, v);
            largest = Math.Max(largest, v ^ y);
            Console.WriteLine($"{v}: best partner {y}, XOR {v ^ y} = {Bits(v ^ y)}");
        }
        Console.WriteLine($"the largest XOR: {largest}");
    }
}

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31
package main

import (
	"fmt"
	"strings"
)

const B = 5 // every number here is below 2^5 = 32

type Node struct {
	children [2]*Node // the 0 child and the 1 child
	number   int      // at the bottom: the number these bits spell
}

func insert(root *Node, v int) {
	node := root
	for b := B - 1; b >= 0; b-- { // the highest bit first
		bit := (v >> b) & 1
		if node.children[bit] == nil {
			node.children[bit] = &Node{}
		}
		node = node.children[bit]
	}
	node.number = v
}

func bestPartner(root *Node, v int) int { // the number y in the trie with the largest v ^ y
	node := root
	for b := B - 1; b >= 0; b-- {
		bit := (v >> b) & 1
		if node.children[1-bit] != nil { // the opposite bit is there: take it
			node = node.children[1-bit]
		} else {
			node = node.children[bit]
		}
	}
	return node.number
}

func main() {
	nums := []int{12, 5, 26, 18, 9}
	root := &Node{}
	for _, v := range nums {
		insert(root, v)
	}
	shown := []string{}
	for _, v := range nums {
		shown = append(shown, fmt.Sprintf("%d (%05b)", v, v))
	}
	fmt.Println("numbers:", strings.Join(shown, ", "))
	largest := 0
	for _, v := range nums {
		y := bestPartner(root, v)
		if v^y > largest {
			largest = v ^ y
		}
		fmt.Printf("%d: best partner %d, XOR %d = %05b\n", v, y, v^y, v^y)
	}
	fmt.Println("the largest XOR:", largest)
}

// numbers: 12 (01100), 5 (00101), 26 (11010), 18 (10010), 9 (01001)
// 12: best partner 18, XOR 30 = 11110
// 5: best partner 26, XOR 31 = 11111
// 26: best partner 5, XOR 31 = 11111
// 18: best partner 12, XOR 30 = 11110
// 9: best partner 18, XOR 27 = 11011
// the largest XOR: 31

5 is 00101, and the walk wants 1, 1, 0, 1, 0: 26, 11010, has all five, so 5 XOR 26 is 11111, 31, the largest XOR there can be in 5 bits. 12, 01100, wants 1, 0, 0, 1, 1: the trie has 1 then 0 (18 and 26 start 1, only 18 goes on with 0), then 18's 0 and 1, and at the last bit 18 has 0 where 12 wanted 1, so the walk takes it anyway: 12 XOR 18 is 11110, 30. No pair beats 31, and the walks found it.

Choose the Opposite Bit. Walk the trie yourself for each number: at every level, choose the branch, and see the XOR build up one bit at a time.

Choose the Opposite Bit: walk the bit trie of the lesson's numbers for a number, choose the branch at every level, and build the largest XOR one bit at a time

Why the highest bit decides

Taking the opposite bit at the top costs nothing, whatever it does to the bits below. A 1 in bit k is worth 2k2^k, and all the bits under it together are worth at most 2k−12^k - 1: 10000 is 16, 01111 is 15. So once the places above are settled, a number with the opposite bit in this place beats every number with the same bit, whatever their lower bits are, and the walk can settle each place for good before looking at the next.

That's also why the trie holds the bits from the highest down. Read from the lowest bit, the same choices settle the cheap bits first, and a cheap 1 can lead the walk away from an expensive one.

Two 5-bit numbers side by side: 10000, 16, with a 1 in its highest place, and 01111, 15, with 1s in all four places below. 1, the highest bit is worth 16; 2, the four bits below it together are worth 15, one less; 3, so the walk settles the highest bit first and never has to come back to it. Focal line: one high bit outweighs every bit below. Title: a higher bit wins.

Numbers under a limit

Maximum XOR With an Element From Array adds a limit to each query: the largest x XOR y with y at most m, or −1 if no number is that small. A trie of all the numbers would offer some that are too big. Instead, answer the queries offline: sort the numbers, sort the queries by their limit, and before each query, insert the numbers its limit now lets in. Each number goes in once, and each query sees exactly the numbers it's allowed. Then put the answers back in the order they were asked:

B = 5


def insert(root, v):
    node = root
    for b in range(B - 1, -1, -1):
        bit = (v >> b) & 1
        if node[bit] is None:
            node[bit] = [None, None]
        node = node[bit]


def best_xor(root, x):                        # the largest x ^ y over the numbers in the trie
    node, xor = root, 0
    for b in range(B - 1, -1, -1):
        bit = (x >> b) & 1
        if node[1 - bit] is not None:
            xor |= 1 << b
            node = node[1 - bit]
        else:
            node = node[bit]
    return xor


nums = sorted([12, 5, 26, 18, 9])
queries = [(5, 20), (7, 10), (30, 4), (1, 30)]   # (x, limit): the largest x ^ y with y at most the limit
answers = [0] * len(queries)
root = [None, None]                           # a node is its two children
k = 0
for q in sorted(range(len(queries)), key=lambda q: queries[q][1]):   # the smallest limit first
    x, limit = queries[q]
    added = []
    while k < len(nums) and nums[k] <= limit: # every number the limit now lets in
        insert(root, nums[k])
        added.append(str(nums[k]))
        k += 1
    answers[q] = best_xor(root, x) if k else -1   # no number at or under the limit
    print(f"limit {limit}: added {' '.join(added) or 'nothing'}, x = {x}: {answers[q]}")
print("answers in the order asked:", " ".join(map(str, answers)))

# limit 4: added nothing, x = 30: -1
# limit 10: added 5 9, x = 7: 14
# limit 20: added 12 18, x = 5: 23
# limit 30: added 26, x = 1: 27
# answers in the order asked: 23 14 -1 27
import java.util.*;

public class Main {
    static final int B = 5;

    static class Node {
        final Node[] children = new Node[2];
    }

    static void insert(Node root, int v) {
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (node.children[bit] == null) node.children[bit] = new Node();
            node = node.children[bit];
        }
    }

    static int bestXor(Node root, int x) {           // the largest x ^ y over the numbers in the trie
        Node node = root;
        int xor = 0;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (node.children[1 - bit] != null) {
                xor |= 1 << b;
                node = node.children[1 - bit];
            } else {
                node = node.children[bit];
            }
        }
        return xor;
    }

    public static void main(String[] args) {
        int[] nums = {12, 5, 26, 18, 9};
        Arrays.sort(nums);
        int[][] queries = {{5, 20}, {7, 10}, {30, 4}, {1, 30}};   // (x, limit): the largest x ^ y with y at most the limit
        Integer[] order = {0, 1, 2, 3};
        Arrays.sort(order, Comparator.comparingInt(q -> queries[q][1]));   // the smallest limit first
        int[] answers = new int[queries.length];
        Node root = new Node();
        int k = 0;
        for (int q : order) {
            int x = queries[q][0], limit = queries[q][1];
            StringJoiner added = new StringJoiner(" ");
            while (k < nums.length && nums[k] <= limit) {   // every number the limit now lets in
                insert(root, nums[k]);
                added.add(String.valueOf(nums[k]));
                k++;
            }
            answers[q] = k > 0 ? bestXor(root, x) : -1;    // no number at or under the limit
            String shown = added.length() == 0 ? "nothing" : added.toString();
            System.out.println("limit " + limit + ": added " + shown + ", x = " + x + ": " + answers[q]);
        }
        StringJoiner all = new StringJoiner(" ");
        for (int a : answers) all.add(String.valueOf(a));
        System.out.println("answers in the order asked: " + all);
    }
}

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27
#include <bits/stdc++.h>
using namespace std;

const int B = 5;

struct Node {
    Node* children[2] = {};
};

void insert(Node* root, int v) {
    Node* node = root;
    for (int b = B - 1; b >= 0; b--) {
        int bit = (v >> b) & 1;
        if (!node->children[bit]) node->children[bit] = new Node();
        node = node->children[bit];
    }
}

int bestXor(Node* root, int x) {              // the largest x ^ y over the numbers in the trie
    Node* node = root;
    int xr = 0;
    for (int b = B - 1; b >= 0; b--) {
        int bit = (x >> b) & 1;
        if (node->children[1 - bit]) {
            xr |= 1 << b;
            node = node->children[1 - bit];
        } else {
            node = node->children[bit];
        }
    }
    return xr;
}

int main() {
    vector<int> nums = {12, 5, 26, 18, 9};
    sort(nums.begin(), nums.end());
    vector<pair<int, int>> queries = {{5, 20}, {7, 10}, {30, 4}, {1, 30}};   // (x, limit): the largest x ^ y with y at most the limit
    vector<int> order = {0, 1, 2, 3};
    sort(order.begin(), order.end(), [&](int a, int b) { return queries[a].second < queries[b].second; });   // the smallest limit first
    vector<int> answers(queries.size());
    Node* root = new Node();
    size_t k = 0;
    for (int q : order) {
        auto [x, limit] = queries[q];
        string added;
        while (k < nums.size() && nums[k] <= limit) {   // every number the limit now lets in
            insert(root, nums[k]);
            added += (added.empty() ? "" : " ") + to_string(nums[k]);
            k++;
        }
        answers[q] = k > 0 ? bestXor(root, x) : -1;    // no number at or under the limit
        cout << "limit " << limit << ": added " << (added.empty() ? "nothing" : added) << ", x = " << x << ": " << answers[q] << "\n";
    }
    cout << "answers in the order asked:";
    for (int a : answers) cout << " " << a;
    cout << "\n";
}

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27
const B = 5;

function insert(root, v) {
    let node = root;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (v >> b) & 1;
        if (node[bit] === null) node[bit] = [null, null];
        node = node[bit];
    }
}

function bestXor(root, x) {                   // the largest x ^ y over the numbers in the trie
    let node = root, xor = 0;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (x >> b) & 1;
        if (node[1 - bit] !== null) {
            xor |= 1 << b;
            node = node[1 - bit];
        } else {
            node = node[bit];
        }
    }
    return xor;
}

const nums = [12, 5, 26, 18, 9].sort((a, b) => a - b);
const queries = [[5, 20], [7, 10], [30, 4], [1, 30]];   // (x, limit): the largest x ^ y with y at most the limit
const answers = new Array(queries.length).fill(0);
const root = [null, null];                    // a node is its two children
let k = 0;
for (const q of [0, 1, 2, 3].sort((a, b) => queries[a][1] - queries[b][1])) {   // the smallest limit first
    const [x, limit] = queries[q];
    const added = [];
    while (k < nums.length && nums[k] <= limit) {   // every number the limit now lets in
        insert(root, nums[k]);
        added.push(nums[k]);
        k++;
    }
    answers[q] = k > 0 ? bestXor(root, x) : -1;     // no number at or under the limit
    console.log(`limit ${limit}: added ${added.join(" ") || "nothing"}, x = ${x}: ${answers[q]}`);
}
console.log("answers in the order asked:", answers.join(" "));

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27
const B = 5;
type BitNode = [BitNode | null, BitNode | null];   // a node is its two children

function insert(root: BitNode, v: number): void {
    let node = root;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (v >> b) & 1;
        if (node[bit] === null) node[bit] = [null, null];
        node = node[bit]!;
    }
}

function bestXor(root: BitNode, x: number): number {   // the largest x ^ y over the numbers in the trie
    let node = root, xor = 0;
    for (let b = B - 1; b >= 0; b--) {
        const bit = (x >> b) & 1;
        if (node[1 - bit] !== null) {
            xor |= 1 << b;
            node = node[1 - bit]!;
        } else {
            node = node[bit]!;
        }
    }
    return xor;
}

const nums = [12, 5, 26, 18, 9].sort((a, b) => a - b);
const queries = [[5, 20], [7, 10], [30, 4], [1, 30]];   // (x, limit): the largest x ^ y with y at most the limit
const answers: number[] = new Array(queries.length).fill(0);
const root: BitNode = [null, null];
let k = 0;
for (const q of [0, 1, 2, 3].sort((a, b) => queries[a][1] - queries[b][1])) {   // the smallest limit first
    const [x, limit] = queries[q];
    const added: number[] = [];
    while (k < nums.length && nums[k] <= limit) {   // every number the limit now lets in
        insert(root, nums[k]);
        added.push(nums[k]);
        k++;
    }
    answers[q] = k > 0 ? bestXor(root, x) : -1;     // no number at or under the limit
    console.log(`limit ${limit}: added ${added.join(" ") || "nothing"}, x = ${x}: ${answers[q]}`);
}
console.log("answers in the order asked:", answers.join(" "));

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27
using System;
using System.Collections.Generic;
using System.Linq;

class Node {
    public readonly Node[] Children = new Node[2];
}

class Program {
    const int B = 5;

    static void Insert(Node root, int v) {
        Node node = root;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (v >> b) & 1;
            if (node.Children[bit] == null) node.Children[bit] = new Node();
            node = node.Children[bit];
        }
    }

    static int BestXor(Node root, int x) {    // the largest x ^ y over the numbers in the trie
        Node node = root;
        int xor = 0;
        for (int b = B - 1; b >= 0; b--) {
            int bit = (x >> b) & 1;
            if (node.Children[1 - bit] != null) {
                xor |= 1 << b;
                node = node.Children[1 - bit];
            } else {
                node = node.Children[bit];
            }
        }
        return xor;
    }

    static void Main() {
        int[] nums = {12, 5, 26, 18, 9};
        Array.Sort(nums);
        int[][] queries = {new[] {5, 20}, new[] {7, 10}, new[] {30, 4}, new[] {1, 30}};   // (x, limit): the largest x ^ y with y at most the limit
        int[] order = Enumerable.Range(0, queries.Length).OrderBy(q => queries[q][1]).ToArray();   // the smallest limit first
        var answers = new int[queries.Length];
        var root = new Node();
        int k = 0;
        foreach (int q in order) {
            int x = queries[q][0], limit = queries[q][1];
            var added = new List<int>();
            while (k < nums.Length && nums[k] <= limit) {   // every number the limit now lets in
                Insert(root, nums[k]);
                added.Add(nums[k]);
                k++;
            }
            answers[q] = k > 0 ? BestXor(root, x) : -1;    // no number at or under the limit
            string shown = added.Count == 0 ? "nothing" : string.Join(" ", added);
            Console.WriteLine($"limit {limit}: added {shown}, x = {x}: {answers[q]}");
        }
        Console.WriteLine("answers in the order asked: " + string.Join(" ", answers));
    }
}

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27
package main

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

const B = 5

type Node struct {
	children [2]*Node
}

func insert(root *Node, v int) {
	node := root
	for b := B - 1; b >= 0; b-- {
		bit := (v >> b) & 1
		if node.children[bit] == nil {
			node.children[bit] = &Node{}
		}
		node = node.children[bit]
	}
}

func bestXor(root *Node, x int) int { // the largest x ^ y over the numbers in the trie
	node, xor := root, 0
	for b := B - 1; b >= 0; b-- {
		bit := (x >> b) & 1
		if node.children[1-bit] != nil {
			xor |= 1 << b
			node = node.children[1-bit]
		} else {
			node = node.children[bit]
		}
	}
	return xor
}

func main() {
	nums := []int{12, 5, 26, 18, 9}
	sort.Ints(nums)
	queries := [][2]int{{5, 20}, {7, 10}, {30, 4}, {1, 30}} // (x, limit): the largest x ^ y with y at most the limit
	order := []int{0, 1, 2, 3}
	sort.Slice(order, func(a, b int) bool { return queries[order[a]][1] < queries[order[b]][1] }) // the smallest limit first
	answers := make([]int, len(queries))
	root := &Node{}
	k := 0
	for _, q := range order {
		x, limit := queries[q][0], queries[q][1]
		added := []string{}
		for k < len(nums) && nums[k] <= limit { // every number the limit now lets in
			insert(root, nums[k])
			added = append(added, strconv.Itoa(nums[k]))
			k++
		}
		if k > 0 {
			answers[q] = bestXor(root, x)
		} else {
			answers[q] = -1 // no number at or under the limit
		}
		shown := strings.Join(added, " ")
		if shown == "" {
			shown = "nothing"
		}
		fmt.Printf("limit %d: added %s, x = %d: %d\n", limit, shown, x, answers[q])
	}
	all := []string{}
	for _, a := range answers {
		all = append(all, strconv.Itoa(a))
	}
	fmt.Println("answers in the order asked:", strings.Join(all, " "))
}

// limit 4: added nothing, x = 30: -1
// limit 10: added 5 9, x = 7: 14
// limit 20: added 12 18, x = 5: 23
// limit 30: added 26, x = 1: 27
// answers in the order asked: 23 14 -1 27

The smallest limit, 4, came first and let nothing in: −1. The limit 10 let in 5 and 9, and 7's best among them was 7 XOR 9, 14. The limit 20 added 12 and 18, and 5's best was 5 XOR 18, 23: 26 would have made 31, but it's over the limit. 26 came in last, for 1: 1 XOR 26 is 27.

The numbers 5, 9, 12, 18 and 26 on a line, sorted, and the four queries sorted by limit: 4, 10, 20, 30. 1, the limit 4 lets nothing in, so x = 30 answers −1; 2, the limit 10 lets in 5 and 9, and x = 7 gets 14; 3, the limit 20 adds 12 and 18, and x = 5 gets 23; 4, the limit 30 adds 26, and x = 1 gets 27. Focal line: each number goes in once, when its limit comes. Title: let the numbers in by limit.

What it costs

Every pairThe bit trie
Largest XOR of n numbersO(n²) XORsO(n · B): B steps to insert, B to ask
MemoryO(1)up to n · B + 1 nodes
q queries with a limitO(q · n)O((n + q) · B) after sorting

B is the width, fixed by the largest value the problem allows: 30 or 31 for numbers below 2302^{30} or 2312^{31}. Each node has only two children, so the trie can live in two arrays of child indexes, one for 0 and one for 1, as the first example did, instead of an object per node.

Spotting a bit trie

Clues that a trie of bits is the tool:

  • The largest (or smallest) XOR of two numbers, or of a number with any of a set.
  • XOR questions asked over and over against a growing set of numbers.
  • A limit on the numbers a query may use: sort and insert as the limit grows.

Near misses:

  • The XOR of everything, or of a range: a running XOR (prefix XOR) answers it, no trie.
  • One XOR question on a small list: every pair is fine when n is a few hundred.
  • The largest sum or AND of two numbers: XOR's "opposite bit" rule doesn't carry over.

Mistakes that look right

Two of these are run below in every language. The others are just as common:

  • Inserting and walking from the lowest bit: the walk settles cheap bits first and can miss the best partner.
  • A width too small: bits above it never enter the trie, and the XOR loses them.
  • Queries with a limit answered against all the numbers: the walk takes numbers over the limit.
  • Asking against an empty trie: the first number has nothing to pair with, and the walk falls off a missing child. Ask from the second number on, as the first example does.
def best_xor(nums, v, width, lowest_first):
    """a trie of the numbers' bits, then the walk that takes the opposite bit where it can"""
    order = list(range(width)) if lowest_first else list(range(width - 1, -1, -1))
    root = [None, None]
    for y in nums:
        node = root
        for b in order:
            bit = (y >> b) & 1
            if node[bit] is None:
                node[bit] = [None, None]
            node = node[bit]
    node, xor = root, 0
    for b in order:
        bit = (v >> b) & 1
        if node[1 - bit] is not None:
            xor |= 1 << b
            node = node[1 - bit]
        else:
            node = node[bit]
    return xor


nums = [12, 5, 26, 18, 9]
for name, width, lowest_first in (("from the highest bit", 5, False), ("from the lowest bit", 5, True),
                                  ("with 4 bits for 5-bit numbers", 4, False)):
    got = {v: best_xor(nums, v, width, lowest_first) for v in nums}
    print(f"{name}: 12 gets {got[12]}, 18 gets {got[18]}, the largest {max(got.values())}")

# from the highest bit: 12 gets 30, 18 gets 30, the largest 31
# from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
# with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
public class Main {
    /** a trie of the numbers' bits, then the walk that takes the opposite bit where it can */
    static int bestXor(int[] nums, int v, int width, boolean lowestFirst) {
        int[] order = new int[width];
        for (int k = 0; k < width; k++) order[k] = lowestFirst ? k : width - 1 - k;
        Object[] root = new Object[2];
        for (int y : nums) {
            Object[] node = root;
            for (int b : order) {
                int bit = (y >> b) & 1;
                if (node[bit] == null) node[bit] = new Object[2];
                node = (Object[]) node[bit];
            }
        }
        Object[] node = root;
        int xor = 0;
        for (int b : order) {
            int bit = (v >> b) & 1;
            if (node[1 - bit] != null) {
                xor |= 1 << b;
                node = (Object[]) node[1 - bit];
            } else {
                node = (Object[]) node[bit];
            }
        }
        return xor;
    }

    public static void main(String[] args) {
        int[] nums = {12, 5, 26, 18, 9};
        String[] names = {"from the highest bit", "from the lowest bit", "with 4 bits for 5-bit numbers"};
        int[] widths = {5, 5, 4};
        boolean[] lowest = {false, true, false};
        for (int k = 0; k < 3; k++) {
            int largest = 0;
            for (int v : nums) largest = Math.max(largest, bestXor(nums, v, widths[k], lowest[k]));
            System.out.println(names[k] + ": 12 gets " + bestXor(nums, 12, widths[k], lowest[k]) + ", 18 gets "
                + bestXor(nums, 18, widths[k], lowest[k]) + ", the largest " + largest);
        }
    }
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* children[2] = {};
};

/** a trie of the numbers' bits, then the walk that takes the opposite bit where it can */
int bestXor(const vector<int>& nums, int v, int width, bool lowestFirst) {
    vector<int> order;
    for (int k = 0; k < width; k++) order.push_back(lowestFirst ? k : width - 1 - k);
    Node* root = new Node();
    for (int y : nums) {
        Node* node = root;
        for (int b : order) {
            int bit = (y >> b) & 1;
            if (!node->children[bit]) node->children[bit] = new Node();
            node = node->children[bit];
        }
    }
    Node* node = root;
    int xr = 0;
    for (int b : order) {
        int bit = (v >> b) & 1;
        if (node->children[1 - bit]) {
            xr |= 1 << b;
            node = node->children[1 - bit];
        } else {
            node = node->children[bit];
        }
    }
    return xr;
}

int main() {
    vector<int> nums = {12, 5, 26, 18, 9};
    vector<tuple<string, int, bool>> ways = {
        {"from the highest bit", 5, false}, {"from the lowest bit", 5, true}, {"with 4 bits for 5-bit numbers", 4, false}};
    for (auto& [name, width, lowest] : ways) {
        int largest = 0;
        for (int v : nums) largest = max(largest, bestXor(nums, v, width, lowest));
        cout << name << ": 12 gets " << bestXor(nums, 12, width, lowest) << ", 18 gets "
             << bestXor(nums, 18, width, lowest) << ", the largest " << largest << "\n";
    }
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
/** a trie of the numbers' bits, then the walk that takes the opposite bit where it can */
function bestXor(nums, v, width, lowestFirst) {
    const order = Array.from({ length: width }, (_, k) => (lowestFirst ? k : width - 1 - k));
    const root = [null, null];
    for (const y of nums) {
        let node = root;
        for (const b of order) {
            const bit = (y >> b) & 1;
            if (node[bit] === null) node[bit] = [null, null];
            node = node[bit];
        }
    }
    let node = root, xor = 0;
    for (const b of order) {
        const bit = (v >> b) & 1;
        if (node[1 - bit] !== null) {
            xor |= 1 << b;
            node = node[1 - bit];
        } else {
            node = node[bit];
        }
    }
    return xor;
}

const nums = [12, 5, 26, 18, 9];
for (const [name, width, lowestFirst] of [["from the highest bit", 5, false], ["from the lowest bit", 5, true],
    ["with 4 bits for 5-bit numbers", 4, false]]) {
    const largest = Math.max(...nums.map((v) => bestXor(nums, v, width, lowestFirst)));
    console.log(`${name}: 12 gets ${bestXor(nums, 12, width, lowestFirst)}, 18 gets ${bestXor(nums, 18, width, lowestFirst)}, the largest ${largest}`);
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
type BitNode = [BitNode | null, BitNode | null];

/** a trie of the numbers' bits, then the walk that takes the opposite bit where it can */
function bestXor(nums: number[], v: number, width: number, lowestFirst: boolean): number {
    const order = Array.from({ length: width }, (_, k) => (lowestFirst ? k : width - 1 - k));
    const root: BitNode = [null, null];
    for (const y of nums) {
        let node = root;
        for (const b of order) {
            const bit = (y >> b) & 1;
            if (node[bit] === null) node[bit] = [null, null];
            node = node[bit]!;
        }
    }
    let node = root, xor = 0;
    for (const b of order) {
        const bit = (v >> b) & 1;
        if (node[1 - bit] !== null) {
            xor |= 1 << b;
            node = node[1 - bit]!;
        } else {
            node = node[bit]!;
        }
    }
    return xor;
}

const nums = [12, 5, 26, 18, 9];
const ways: [string, number, boolean][] = [["from the highest bit", 5, false], ["from the lowest bit", 5, true],
    ["with 4 bits for 5-bit numbers", 4, false]];
for (const [name, width, lowestFirst] of ways) {
    const largest = Math.max(...nums.map((v) => bestXor(nums, v, width, lowestFirst)));
    console.log(`${name}: 12 gets ${bestXor(nums, 12, width, lowestFirst)}, 18 gets ${bestXor(nums, 18, width, lowestFirst)}, the largest ${largest}`);
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
using System;
using System.Linq;

class Node {
    public readonly Node[] Children = new Node[2];
}

class Program {
    /** a trie of the numbers' bits, then the walk that takes the opposite bit where it can */
    static int BestXor(int[] nums, int v, int width, bool lowestFirst) {
        int[] order = Enumerable.Range(0, width).Select(k => lowestFirst ? k : width - 1 - k).ToArray();
        var root = new Node();
        foreach (int y in nums) {
            Node node = root;
            foreach (int b in order) {
                int bit = (y >> b) & 1;
                if (node.Children[bit] == null) node.Children[bit] = new Node();
                node = node.Children[bit];
            }
        }
        Node at = root;
        int xor = 0;
        foreach (int b in order) {
            int bit = (v >> b) & 1;
            if (at.Children[1 - bit] != null) {
                xor |= 1 << b;
                at = at.Children[1 - bit];
            } else {
                at = at.Children[bit];
            }
        }
        return xor;
    }

    static void Main() {
        int[] nums = {12, 5, 26, 18, 9};
        var ways = new (string, int, bool)[] {
            ("from the highest bit", 5, false), ("from the lowest bit", 5, true), ("with 4 bits for 5-bit numbers", 4, false)};
        foreach (var (name, width, lowest) in ways) {
            int largest = nums.Max(v => BestXor(nums, v, width, lowest));
            Console.WriteLine($"{name}: 12 gets {BestXor(nums, 12, width, lowest)}, 18 gets {BestXor(nums, 18, width, lowest)}, the largest {largest}");
        }
    }
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15
package main

import "fmt"

type Node struct {
	children [2]*Node
}

// bestXor builds a trie of the numbers' bits, then walks it taking the opposite bit where it can
func bestXor(nums []int, v, width int, lowestFirst bool) int {
	order := make([]int, width)
	for k := range order {
		if lowestFirst {
			order[k] = k
		} else {
			order[k] = width - 1 - k
		}
	}
	root := &Node{}
	for _, y := range nums {
		node := root
		for _, b := range order {
			bit := (y >> b) & 1
			if node.children[bit] == nil {
				node.children[bit] = &Node{}
			}
			node = node.children[bit]
		}
	}
	node, xor := root, 0
	for _, b := range order {
		bit := (v >> b) & 1
		if node.children[1-bit] != nil {
			xor |= 1 << b
			node = node.children[1-bit]
		} else {
			node = node.children[bit]
		}
	}
	return xor
}

func main() {
	nums := []int{12, 5, 26, 18, 9}
	ways := []struct {
		name   string
		width  int
		lowest bool
	}{{"from the highest bit", 5, false}, {"from the lowest bit", 5, true}, {"with 4 bits for 5-bit numbers", 4, false}}
	for _, way := range ways {
		largest := 0
		for _, v := range nums {
			if got := bestXor(nums, v, way.width, way.lowest); got > largest {
				largest = got
			}
		}
		fmt.Printf("%s: 12 gets %d, 18 gets %d, the largest %d\n", way.name, bestXor(nums, 12, way.width, way.lowest),
			bestXor(nums, 18, way.width, way.lowest), largest)
	}
}

// from the highest bit: 12 gets 30, 18 gets 30, the largest 31
// from the lowest bit: 12 gets 5, 18 gets 23, the largest 31
// with 4 bits for 5-bit numbers: 12 gets 14, 18 gets 14, the largest 15

From the lowest bit, 12's best came out as 5 and 18's as 23, where 30 was there for both. The largest still came out 31, but only because 5 and 26 differ in every bit. With 4 bits for these 5-bit numbers, the top bit, worth 16, never entered the trie, and the largest came out 15.

Check yourself

Quiz

1 / 6

Multiple choice

A bit trie holds numbers below 2^20, inserted from the highest bit. How many levels does each insert walk?

Practice

The section's problems for this lesson, each mapped to the idea it trains:

  1. Bitwise Foundations for Tries: the bit trie and the opposite-bit walk, from scratch.
  2. Maximum XOR of Two Numbers in an Array: insert each number and ask with it.
  3. Maximum XOR With an Element From Array: queries with a limit, sorted and answered offline.