What is Hamming distance

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

 

Example 1

Input: x = 5, y = 5

Output: 0

Example 2

Input: x = 1, y = 3

Output: 1

As usual, we're are string from understanding the problem. The first question we need to answer is. What is the Hamming distance?

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

Let's try to find the Hamming distance for 10 and 15. To find the Hamming distance, we need to compare the numbers in binary. 10 = 00001010 (in binary) and 15 = 00001111 (in binary). The Hamming distance between 10 and 15 is 2 because they differ in two bits

 

Approach

Before starting to solve the problem, you need to know bitwise operators. To find the Hamming distance, we can start comparing from right to left bit by bit.

• if bits are different
  • increment the result
• shift each number on one bit to the right

Code

    public int HammingDistance(uint x, uint y)
    {
        if (x == y)
        {
            return 0;
        }

        int result = 0;
        while (x != 0 || y != 0)
        {
            if ((x & 1) != (y & 1))
            {
                result++;
            }

            x = x >> 1;
            y = y >> 1;
        }

        return result;
    }