Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Binary tries: choose a maximum-XOR fingerprint

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A binary trie stores one fixed-width unsigned integer as a root-to-leaf sequence of bits, most significant first. Every node counts how many stored values pass through it, so duplicates share a path. To maximize XOR with a query, follow the opposite query bit whenever that branch exists; a higher XOR bit outweighs every combination of lower bits. The path reconstructs an actual stored partner, and the method returns that partner with its XOR score. Removal decrements counts and drops an empty suffix branch. This is a multiset of integer fingerprints, not an XOR linear basis: the answer must be one value actually stored, rather than a XOR combination of several values.

Operational case

Store 19, 47, 61, 83, and a second 47 as eight-bit fingerprints. For query 26, the best stored partner is 83, giving XOR score 73. Removing one 47 leaves one copy; removing it again leaves zero. A missing removal raises. An empty index cannot supply a partner and raises instead of inventing zero. Both inserted values and queries must fit the declared unsigned width. Without the width check, Python negative integers and wider positive values would not have the fixed bit paths this trie assumes.

Working Python program

python
"""Fixed-width unsigned integer multiset with maximum-XOR partner queries."""

from dataclasses import dataclass, field


@dataclass
class BitNode:
    count: int = 0
    children: dict[int, "BitNode"] = field(default_factory=dict)


class AssetFingerprintTrie:
    def __init__(self, bit_width: int):
        if bit_width < 1:
            raise ValueError("bit width must be positive")
        self.bit_width = bit_width
        self.root = BitNode()

    def _check(self, fingerprint: int) -> None:
        if not isinstance(fingerprint, int) or isinstance(fingerprint, bool) or not 0 <= fingerprint < 1 << self.bit_width:
            raise ValueError("fingerprint exceeds the unsigned width")

    def add(self, fingerprint: int) -> None:
        self._check(fingerprint)
        node = self.root
        node.count += 1
        for shift in range(self.bit_width - 1, -1, -1):
            bit = (fingerprint >> shift) & 1
            node = node.children.setdefault(bit, BitNode())
            node.count += 1

    def count(self, fingerprint: int) -> int:
        self._check(fingerprint)
        node = self.root
        for shift in range(self.bit_width - 1, -1, -1):
            node = node.children.get((fingerprint >> shift) & 1)
            if node is None:
                return 0
        return node.count

    def remove(self, fingerprint: int) -> None:
        if self.count(fingerprint) == 0:
            raise KeyError(fingerprint)
        node = self.root
        node.count -= 1
        for shift in range(self.bit_width - 1, -1, -1):
            bit = (fingerprint >> shift) & 1
            child = node.children[bit]
            child.count -= 1
            if child.count == 0:
                del node.children[bit]
                return
            node = child

    def best_xor_partner(self, fingerprint: int) -> tuple[int, int]:
        self._check(fingerprint)
        if self.root.count == 0:
            raise ValueError("no fingerprints stored")
        node = self.root
        partner = 0
        for shift in range(self.bit_width - 1, -1, -1):
            wanted = 1 - ((fingerprint >> shift) & 1)
            chosen = wanted if wanted in node.children else 1 - wanted
            partner |= chosen << shift
            node = node.children[chosen]
        return partner, fingerprint ^ partner


fingerprints = AssetFingerprintTrie(8)
for fingerprint in (19, 47, 61, 83, 47):
    fingerprints.add(fingerprint)
print(fingerprints.best_xor_partner(26))
fingerprints.remove(47)
print(fingerprints.count(47))
fingerprints.remove(47)
print(fingerprints.count(47))

Output

Output
(83, 73)
1
0

Time, space, and tradeoff

With bit width B, insertion, count, removal, and best-partner search each visit exactly B levels: O(B) time. Storage is O(U B) nodes in the worst case for U distinct stored values, with shared prefixes reducing actual use. Duplicate occurrences change counts without adding new branches. Removal may free an unused suffix, but Python object dictionaries carry overhead that can exceed a flat array for small sets. Greedy maximum-XOR search gives one stored maximizing partner; if several partners tie in score, the bit path still determines the numerical partner. This implementation is single-threaded and does not provide a concurrent snapshot.

Common Mistakes

  • Do not accept a wider or negative integer after constructing a fixed-width trie.
  • Do not erase a shared branch when removing only one duplicate.
  • Do not return an XOR combination that was never stored as a partner.
  • Do not query a maximum partner from an empty multiset.

Connected lessons

Apply the invariant in the asset and depot audit project, then check the operations quiz.

Binary radix routing: choose the longest matching prefix adds a keyed lookup comparison.

Range XOR bases: merge linear spans in a segment tree examines a related structure with a different operation boundary.

Patricia binary routing: compress chains without losing prefix matches examines a related structure with a different operation boundary.

data structures
range-query-structures
Storage details