On this page
Description
The largest XOR of two numbers in an array: all pairs is O(n^2). XOR rewards differing bits, and the highest bit matters most - a 1 at bit i beats any combination of lower bits. Storing numbers bit by bit in a trie lets a greedy walk pick, for each number, the partner that differs at the highest possible bit.
This skill covers the binary trie: fixed-width bits inserted from the top, and a greedy walk that takes the opposite bit whenever it exists. It also covers answering queries that come with a limit offline, by sorting the queries and inserting values as the limit grows.
We'll go from simple to more technical:
- The pattern: maximum XOR of two numbers with a bit trie and a greedy walk.
- A second flavor: queries with a limit, answered offline in sorted order.
- Where bit tries run (IP routing, Kademlia's XOR distance).
- What breaks it: inconsistent widths, too few bits, online order, empty tries.
The approach
Java
static final int HIGH_BIT = 29; // values < 2^30: bits 29..0
void insert(int num) {
BitNode node = root;
for (int b = HIGH_BIT; b >= 0; b--) { // most significant bit first
int bit = (num >> b) & 1;
if (node.next[bit] == null) node.next[bit] = new BitNode();
node = node.next[bit];
}
}
int maxXorWith(int num) {
BitNode node = root;
int result = 0;
for (int b = HIGH_BIT; b >= 0; b--) {
int bit = (num >> b) & 1;
if (node.next[1 - bit] != null) { // the opposite bit gives a 1 here
result |= 1 << b;
node = node.next[1 - bit];
} else {
node = node.next[bit];
}
}
return result;
}
Python
HIGH_BIT = 29 # values < 2^30: bits 29..0
def insert(num: int) -> None:
node = root
for b in range(HIGH_BIT, -1, -1): # most significant bit first
bit = (num >> b) & 1
if node.next[bit] is None:
node.next[bit] = BitNode()
node = node.next[bit]
def max_xor_with(num: int) -> int:
node = root
result = 0
for b in range(HIGH_BIT, -1, -1):
bit = (num >> b) & 1
if node.next[1 - bit] is not None: # the opposite bit gives a 1 here
result |= 1 << b
node = node.next[1 - bit]
else:
node = node.next[bit]
return result
Insert every number, then take the best maxXorWith over all of them: O(n x bits). The greedy is exact because 2^b is larger than the sum of all lower bits (2^b - 1), so winning the highest possible bit is always right. Every number must be inserted with the same width, starting at the highest bit any value can have - for values below 2^30 that's bit 29. Starting too low (say bit 15) silently drops the high bits of large values.
A second flavor: queries with a limit, answered offline
"For each query (x, m), the maximum of x XOR v over array values v <= m." Rebuilding the trie per query is O(n) each. Instead, sort the values, sort the queries by m, and insert values into the trie only as the limit grows:
Java
Arrays.sort(values);
Integer[] order = /* query indices sorted by m */;
int p = 0;
for (int qi : order) {
while (p < values.length && values[p] <= queries[qi][1]) insert(values[p++]); // everything allowed so far
answers[qi] = (p == 0) ? -1 : maxXorWith(queries[qi][0]); // nothing <= m: -1
}
Python
values.sort()
order = sorted(range(len(queries)), key=lambda i: queries[i][1]) # query indices sorted by m
p = 0
for qi in order:
x, m = queries[qi]
while p < len(values) and values[p] <= m:
insert(values[p]) # everything allowed so far
p += 1
answers[qi] = -1 if p == 0 else max_xor_with(x) # nothing <= m: -1
When query qi is answered, the trie contains exactly the values <= its limit. Processing queries in input order breaks that: a large limit inserts values that a later query with a small limit must not see. Answers are written back by the original index.
Where you'll see it
IP routers store network prefixes in binary tries (Patricia tries) and walk destination addresses bit by bit; XOR-distance lookups in the Kademlia DHT (used by BitTorrent's peer discovery) organize peers by the length of the shared bit prefix, the same structure.
Which tool for which job?
| You need | Use |
|---|---|
| The max XOR of two numbers | a bit trie and a greedy walk |
| The same without a trie | bit-by-bit prefix hash sets |
| The max XOR of any subarray | prefix XORs inserted into a bit trie |
| How many pairs have XOR below k | a bit trie with subtree counts |
| Queries with a limit on the values | offline: sort queries and values, insert as the limit grows |
| The max XOR of any subset | a linear basis over GF(2), not a trie |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Different widths per number | bits land at the wrong depths | the same fixed width for every number |
| Starting below the highest bit | starting at bit 15 gave 30 instead of 1048606 | start at the top bit the constraints allow |
| Limited queries in input order | values over a later query's limit are already in | sort queries by limit |
| Querying an empty trie | a null walk, or a made-up answer | return -1 when nothing is allowed |
| A pair trie for "any subset" | [1, 2, 4] gives 6 instead of 7 | a linear basis |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why is taking the opposite bit at the highest possible position always right?
Show answer
A 1 at bit b is worth 2^b, more than all lower bits together (2^b - 1). No choice at lower bits can make up for losing a higher one.
2. Why must every number be inserted with the same width?
Show answer
Depth in the trie stands for bit position. If some numbers start at a lower bit, their bits sit at the wrong depths and the greedy compares bits of different significance.
3. Why sort the queries by their limit in the offline version?
Show answer
So values can be inserted once, in increasing order, as the limit grows - the trie then holds exactly the values allowed for the current query. In input order, a large limit would insert values a later small-limit query must not use.
Key takeaways
- Insert fixed-width bits from the top; prefer the opposite bit at each level.
- The greedy is exact: 2^b > 2^b - 1.
- Start at the highest bit the values can have.
- Limited queries: sort values and queries, insert as the limit grows, answer by original index.