Efficient Hamming Distance Algorithms Between Two Integers in C++

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

For example, given two integers x=1 and y=4, the hamming distance between them is 2:

1   (0 0 0 1)
4   (0 1 0 0)
       ^   ^

We can use the XOR (Exclusive OR) to make this counting easier. The value of x^y stores the difference where the difference is the bit 1. The native C/C++ implementation will be:

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z  = x ^ y;
        int r = 0;
        for (; z > 0; z >>= 1) {
            r += z & 1;
        }
        return r;
    }
};

With C++ STL (assume both integers are 32-bit):

class Solution {
public:
    int hammingDistance(int x, int y) {
        return bitset<32>(x^y).count();
    }
};

And the C++ intrinsic functions offers:

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x^y);
    }
};

Another faster bit-counting approach, as described in A Faster Approach to Count Set Bits in a 32-bit Integer:

class Solution {
public:
    int hammingDistance(int x, int y) {
        int i  = x ^ y;
        i = i - ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i + (i >> 4)) & 0x0f0f0f0f;
        i = i + (i >> 8);
        i = i + (i >> 16);
        return i & 0x3f;        
    }
};

Hamming Weight / Hamming Distance Algorithms

Here are the posts related to Hamming Distance (XOR, The number of different bits):

• A faster approach to count set bits in a 32-bit integer
• Teaching Kids Programming – Minimum Bit Flips to Convert Number (Hamming Distance)
• GoLang: Compute the Hamming Distance
• How to Sort List by Hamming Weight in C++?
• Teaching Kids Programming – Compute the Hamming Distance of Two Integers
• Compute the Total Hamming Distance between All Pairs of Integers
• The Hamming Distance Implementation in Javascript
• Hamming Distance between Two Integers
• Compute Number of 1’s Bits in C/C++
• Teaching Kids Programming – Sort List by Hamming Weight

–EOF (The Ultimate Computing & Technology Blog) —