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;
    }
};

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();
    }
};

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);
    }
};

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;        
    }
};

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):

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...

591 words
Last Post: C++ Coding Exercise - Use HashTable/Priority Queue to Compute the Relative Ranks
Next Post: Software Engineer Interview Tips - Using Hashtable to Reduce Runtime Complexity

The Permanent URL is: Efficient Hamming Distance Algorithms Between Two Integers in C++

Algorithms, Blockchain and Cloud

Efficient Hamming Distance Algorithms Between Two Integers in C++

Hamming Weight / Hamming Distance Algorithms

Leave a Reply

Hamming Weight / Hamming Distance Algorithms

Related posts:

Leave a Reply