Hamming distance

Count how many bit positions differ between two numbers by XORing them and counting the set bits.

The idea

XOR gives a 1 wherever two bits disagree and a 0 wherever they agree, so x ^ y has exactly one set bit for every position x and y differ in. Counting those set bits, with the same n & (n - 1) trick as Count set bits, gives the Hamming distance directly.

Code

public static int HammingDistance(int x, int y) {
    int xorValue = x ^ y; // a 1 marks every bit where x and y differ
    int distance = 0;
    while (xorValue != 0) {
        xorValue &= xorValue - 1; // clear the lowest set bit
        distance++;
    }
    return distance;
}

Tips

• The Hamming distance is 0 exactly when x equals y, since then x ^ y is 0.
• This generalizes to any fixed-width data, not just integers, wherever "how different are these two bit patterns" matters.

In the .NET library

Counting set bits in x ^ y is exactly the Count set bits lesson applied to one extra value; the two lessons share the same clearing loop.