# Calculate Hamming distance between integers with bitwise operations

I recently learned about the Hamming distance. The use-case I found it through was actually working with integers instead of strings, yet its implementation was using string comparison. I was pretty sure it could be done with bitwise operations, and from what I can tell, my implementation is successful.

public int HammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while (xor > 0) {
distance++;
xor &= xor - 1;
}

return distance;
}


However, I can't help but wonder if this makes the code harder to understand for others. Additionally, is there a way to eliminate the while loop but still count the number of set bits in the xor result in a more efficient manner?

Feel free to test it out on .NET Fiddle.

I was pretty sure it could be done with bitwise operations

You are right.

my implementation is successful

No. Think of negative x (or negative y). The loop would terminate immediately.

if this makes the code harder to understand for others

No. Anybody who understands Hamming distance shall understand this bit-fiddling.

is there a way to eliminate the while loop

I don't know a portable way. For the native integral datatypes, all major architectures have a popcount instruction. gcc offers it as a __builtin_popcount. offers std::popcount. In all mainstream architectures both map to a single instruction. I am sure that does not lag.

For the integral larger than native (like BigInteger and the family), the answer is no.

• BTW the built-in popcount function in C# is found in System.Numerics.BitOperations.PopCount (Core 3.0 and later) Feb 13, 2022 at 9:01