Bitwise and Otherwise: Understanding XOR Distance

Bitwise and Otherwise: Understanding XOR Distance

Maneshwar is developing a Micro AI code reviewer called git-lrc, which operates on every commit and is available for free on GitHub. He encourages developers to try it out and provide feedback. While discussing XOR, he came across the term "XOR distance" in an article about P2P networking. At first, he dismissed it as two unrelated concepts combined, but upon learning how it works, he discovered it's a simple and useful idea that can be easily misunderstood.

XOR distance between two IDs is calculated by performing a bitwise XOR operation on their binary representations. The resulting number represents the distance, with larger numbers indicating greater distance and smaller numbers indicating closer proximity. This concept may seem counterintuitive at first, as it doesn't consider the physical location of the nodes.

To understand XOR distance, one must first grasp how XOR works. XOR (exclusive or) compares two bits and returns 1 if they differ and 0 if they are the same. When applied to two IDs, XOR distance measures how different their binary representations are. For example, if A = 1100 and B = 1010, their XOR result is 0110, which equals 6 in decimal. Thus, the XOR distance between A and B is 6.

Mathematically, XOR distance satisfies three properties that define a proper metric:

1. distance(A, A) = 0 (a node is zero distance from itself)

2. Symmetry: A XOR B = B XOR A (the order of nodes doesn't matter)

3. Triangle inequality: distance(A, C) ≤ distance(A, B) + distance(B, C) (hopping toward nodes with smaller distances will eventually lead to the target)

However, XOR distance differs from Hamming distance, which simply counts the number of differing bits without considering their positions. This distinction is crucial because XOR distance takes into account the location of the differing bits, giving more weight to differences in the leftmost (high) bits.

In practical applications, XOR distance is used in algorithms like Kademlia, which organizes a node's routing table based on the distance to other nodes. Each node maintains a set of buckets, each corresponding to a range of distances, containing a few peers within that distance. This allows for efficient lookup and routing within the network.

Interestingly, XOR distance doesn't necessarily correlate with physical proximity. Two nodes located far apart can have a small XOR distance if their hashed IDs share a long bit prefix. Conversely, nodes in the same physical location may have a large XOR distance if their IDs differ significantly in the most significant bits.