4
\$\begingroup\$

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.

\$\endgroup\$

1 Answer 1

6
\$\begingroup\$

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.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ BTW the built-in popcount function in C# is found in System.Numerics.BitOperations.PopCount (Core 3.0 and later) \$\endgroup\$
    – harold
    Feb 13, 2022 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.