Bitwise and Otherwise: Understanding XOR Distance

Developer Maneshwar explains XOR distance, a metric used in peer-to-peer networks like Kademlia, in a technical blog post. The post breaks down how XOR distance is computed, why it qualifies as a proper distance metric, and how it underpins routing tables in systems like BitTorrent's DHT, IPFS, and Ethereum. It includes code examples and a bucket_index function to illustrate how nodes organize peers by distance.

Hello, I'm Maneshwar. I'm building git-lrc, a Micro AI code reviewer that runs on every commit. It is free and source-available on Github. Star git-lrc to help devs discover the project. Do give it a try and share your feedback. I knew XOR. Truth tables, bit flips, the whole deal, nothing new there. Then I was reading some article about P2P networking and ran into the phrase "XOR distance" and just kind of stopped. XOR I know. Distance I know. XOR distance ? That's not a thing, that's two things wearing a trenchcoat. So I went and actually learned how it works, and it turns out it's one of those ideas that's simple once it clicks and mildly infuriating right up until it does. So let's do this properly. We're going to talk about bits, buckets, and why your node's "neighbors" have nothing to do with where they physically live. XOR distance between two IDs is just: XOR their bits together, read the result as a number. That number is your "distance." Bigger number, farther apart. Smaller number, closer. That's it. That's the tweet. Obviously that's not satisfying, so let's actually build it up. XOR exclusive or looks at two bits and asks one question: "do you two agree?" | A | B | A XOR B | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | Same bits, you get 0. Different bits, you get 1. XOR is basically the "spot the difference" operator of computer science. Now take two IDs in real systems these are 160-bit or 256-bit hashes, but let's use 4 bits so nobody has to squint : A = 1100 B = 1010 ---- 0110 this is the XOR Read 0110 as a plain binary number and you get 6. So distance A, B = 6. Congrats, you just computed an XOR distance by hand, you can put that on your resume now. Math is picky about the word "distance." For something to count as a proper metric, it needs three properties, and XOR happens to nail all three, which honestly feels like a happy accident but isn't. That third property is the whole reason this isn't just a cute math trick, it's what makes routing converge . Here's the part that trips people up. XOR distance isn't "count how many bits differ" that's Hamming distance, a different and much less useful cousin . XOR distance cares about where the differing bits are, because it's read as a number, and in numbers, the leftmost digit matters way more than the rightmost one. 1000 XOR 0000 = 1000 = 8 <- disagree on the leftmost high bit 0000 XOR 0001 = 0001 = 1 <- disagree on the rightmost low bit Both pairs differ in exactly one bit. One of them is 8x "farther" than the other. Same amount of disagreement, wildly different distance, all because of where the disagreement lives. Here's roughly how that feels, emotionally: Enough theory, let's compute this for real: php def xor distance a: int, b: int - int: return a ^ b def bucket index distance: int - int: """Which 'bucket' this distance falls into, i.e. index of the highest set bit. This is the thing Kademlia uses to organize its routing table.""" return distance.bit length - 1 if distance else -1 A = 0b1100 B = 0b1010 C = 0b1101 print xor distance A, B 6 - pretty far print xor distance A, C 1 - very close print bucket index xor distance A, B 2 print bucket index xor distance A, C 0 The bucket index function is the sneaky important part. It tells you how far in terms of "shared prefix length." A distance that falls in a high bucket means the IDs barely agree on anything at the front. A distance in bucket 0 means they agree on almost everything except the last bit. This bucketing is literally how Kademlia the algorithm behind BitTorrent's DHT, IPFS, and Ethereum's node discovery organizes who a node bothers to remember. Every node keeps a set of buckets, one per "distance range," and each bucket holds a few peers at that rough distance. Think of it like this: You keep detailed, well-maintained knowledge of nodes close to you, and increasingly fuzzy, "eh, good enough" knowledge of nodes far away. It's basically how your own brain works with acquaintances: you remember your best friend's birthday, you remember that one guy from a conference exists. Say you want to find the node closest to some target ID T , and you're not there yet. You ask whoever you currently know that's closest to T . They, in turn, know someone closer to T than you do because of how the buckets are structured , and they hand you that contact. Repeat. Because of the triangle inequality, each hop is guaranteed to strictly shrink your distance to T . In practice this converges in roughly O log n hops for a network of n nodes, because each hop tends to fix another bit of agreement with the target. No coordinates, no GPS, no "which continent is this peer even on," just pure bit math. This is the bit that messes with people's intuition the most, because we're all trained to think "distance" means physical distance. A node in Bengaluru and a node in Reykjavik can have a tiny XOR distance if their hashed IDs happen to share a long bit prefix, purely by coincidence of hashing. Meanwhile two servers sitting in the same rack can be maximally far apart in XOR space if their IDs hash unluckily. And honestly, that's kind of the whole point. XOR distance throws away geography entirely and replaces it with something that's provably well behaved for routing, at the cost of being completely unintuitive to a human looking at a map. Worth it. If you want to go further down the hole: XOR distance isn't really "distance" in any sense your GPS would recognize, it's a purpose-built mathematical ruler that happens to satisfy exactly the properties routing needs: zero self-distance, symmetry, and a triangle inequality that guarantees convergence. Once that clicks, a huge chunk of how DHTs work stops feeling like magic and starts feeling like, well, bit flips with really good manners. Anyway, that's XOR distance. Go forth and route responsibly. AI agents write code fast. They also silently remove logic, change behavior, and introduce bugs — without telling you. You often find out in production. git-lrc fixes this. It hooks into git commit and reviews every diff before it lands. 60-second setup. Completely free. Any feedback or contributors are welcome It's online, source-available, and ready for anyone to use. ⭐ Star it on GitHub: | 🇩🇰 Dansk https://github.com/HexmosTech/git-lrc/readme/README.da.md | 🇪🇸 Español https://github.com/HexmosTech/git-lrc/readme/README.es.md | 🇮🇷 Farsi https://github.com/HexmosTech/git-lrc/readme/README.fa.md | 🇫🇮 Suomi https://github.com/HexmosTech/git-lrc/readme/README.fi.md | 🇯🇵 日本語 https://github.com/HexmosTech/git-lrc/readme/README.ja.md | 🇳🇴 Norsk https://github.com/HexmosTech/git-lrc/readme/README.nn.md | 🇵🇹 Português https://github.com/HexmosTech/git-lrc/readme/README.pt.md | 🇷🇺 Русский https://github.com/HexmosTech/git-lrc/readme/README.ru.md | 🇦🇱 Shqip https://github.com/HexmosTech/git-lrc/readme/README.sq.md | 🇨🇳 中文 https://github.com/HexmosTech/git-lrc/readme/README.zh.md | 🇮🇳 हिन्दी https://github.com/HexmosTech/git-lrc/readme/README.hi.md | GenAI today is a race car without brakes . It accelerates fast -- you describe something, and large blocks of code appear instantly. But AI agents silently break things : they remove logic, relax constraints, introduce expensive cloud calls, leak credentials, and change behavior -- without telling you. You often find out in production. git-lrc is your braking system. It hooks into git commit and runs an AI review on every diff In short, git-lrc helps Prevent Outages, Breaches, and Technical Debt Before They Happen At a glance: 10 risk categories https://github.com/HexmosTech/git-lrc what-git-lrc-checks-for · 100+ failure patterns tracked https://github.com/HexmosTech/git-lrc what-git-lrc-checks-for · every commit…