Hamming distance

The number of bit positions at which two equal-length words differ. In code it is one line built from the spoke's most-studied operation:

hamming(a, b) = popcount(a XOR b)

XOR sets exactly the differing bits; popcount counts them. Hamming weight is the special case against zero: weight(a) = hamming(a, 0).

Why it is the cheapest interesting distance

On an Intel x86 CPU with AVX-512 and VPOPCNTDQ, a 512-bit Hamming distance is one ZMM register, one XOR, one popcount, one horizontal sum — about 5 nanoseconds valyu-billion-scale-vector-index. A floating-point dot product over the same width costs an order of magnitude more and, per the same source, "doesn't pin cleanly into registers in the same way."

That gap is why binary codes exist as an engineering choice rather than a curiosity. Quantize a float embedding down to 512 bits and you lose precision, but the comparison becomes an integer operation the hardware already has an instruction for, and 64 bytes fits in a register.

What a cheap primitive changes

When the innermost operation costs 5 ns, the algorithm above it can be dumber. That is the finding in valyu-billion-scale-vector-index: at index-build time an exact brute-force sweep over every candidate beat a navigable-graph search that visits far fewer, because each graph visit costs 30–100 ns and gets worse as the structure outgrows cache. Cheap primitive, flat loop, more total work, less total time.

This is the same trade the spoke keeps meeting from the other direction. xor-swap loses to a temp variable because the clever version has a serial dependency the hardware hates; brute-force Hamming beats graph traversal because the dumb version is a straight line the hardware loves. The question is never how few operations, but which operations and in what shape.

Where it is used

Error-correcting codes (the original setting), similarity hashing (SimHash), binary embeddings in vector search, bitboard and bitset comparisons, and any content-addressed dedup over hashes. population-count carries the rest of the application list.

Related

population-count · valyu-billion-scale-vector-index · bit-manipulation · swar · hamming-weight-wikipedia · xor-swap