maxcian der TechBlog

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

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 2³¹.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

---

熟悉bit operattions

ref: http://acm.nudt.edu.cn/~twcourse/BitwiseOperation.html

簡而言之，Hamming distance為比較兩個等長字串、兩個整數之間有多少個bit不相同。

剛好可以使用bit operation中的XOR運算子來了解兩個binary之間有多少個bit相異。

以下在function中加入視覺化輸出理解兩個binary分別轉成二進位後長甚麼樣子、經過XOR後長甚麼樣子(diff_bits)、每一步運算後(diff_bits)長甚麼樣子。

#include <bitset>
int hammingDistance(int x, int y) 
{
    int diff_bits = x ^ y; // x OR y
    int count = 0; // number of diff. bit
    std::cout << "  x: " << std::bitset<32>(x) << endl;
    std::cout << "  x: " << std::bitset<32>(y) << endl;
    while (diff_bits)
    {
        std::cout << "x^y: " << std::bitset<32>(diff_bits) << endl;
        if (diff_bits & 1 == 1)
        {
            ++count;
            cout << "\thit" << endl;
        }
        else
            cout << "\tmiss" << endl;

        diff_bits = diff_bits >> 1;
    }
    return count;
}
int main(int argc, char* argv[])
{
    cout << hammingDistance(atoi(argv[1]),atoi(argv[2])) << endl;
}