Hamming Distance

What is Hamming Distance?

Hamming distance is Technically defined as the number of bits in the same position that differs in two numbers. Let us delve into a new way of finding the distance between two numbers.

Example

Input

To find the hamming distance between 4 and 14

4 and 14

4              0100

14            1110

Output

Hamming distance=2

Let us look at a pictorial representation for two seven-bit numbers.

When is the XOR of two bits 1?

Only if the bits are different. After doing the XOR operation we will have 1 at each location the bits are different. So, we will count the number of set bits.

How should we do that?

The number of set bits in a number is called the Hamming Weight. We have a post on the above topic too but to save the reader the pain of flipping through posts I will give an overview of the easiest approach to do so.

First strengthening our game with a few smart points

• We know that an accepted integer can be maximum 32 bits long
• a&1=1 1&0=0

Keeping these things in sight.

• We loop through the number until we encounter a zero
• We perform AND with the rightmost bit
  • If the and operation gives us 1
    • The bit is set i.e 1
    • Increment the count variable by 1
  • If the and operation gives us 0
    • The bit is not set i.e 0
• The count yields the number of set bits

Now, that we are a little clear about how things work. Let us look into the code

Implementation

Java Code For Hamming Distance

class Solution 
{
    public int hammingDistance(int x, int y) 
    {
    int num=x^y;
    int ct=0;
    while(num!=0)
    {
        num=num&(num-1);
        ct++;
    }
    return ct;
    }
}

C++ Code For Hamming Distance

public:
    int dist(int num1,int num2)
    {
        int xor=num1^num2;
        //The dissimilar bits will have 1 after XORing
        int ans=0;
        //Counting the number of 1s/set bits
        while(xor!=0)
        {
            ans=ans+(xor&1);
            xor=xor>>1;
        }
        return ans;
    }

4 14

2

This was all about Hamming distance!

Complexity Analysis

The time complexity of the above approach=O(n)

Space Complexity=O(1)

Why and How?

• When we XOR both bits. The time complexity for the operation is O(1)
• While trying to find the number of set bits
  • We maintain a variable to store the set bits
  • We iterate through the XORed product
    • Increment the variable as we find a set bit
• Thus making the time complexity as linear/O(n)
• We use only one variable for the XOR making the space complexity O(1)

Now that we have done it for two binary numbers let us expand our approach to strings.

Read On!

Check whether strings are k distance apart or not(Opens in a new browser tab)

References