# Hamming Distance  Difficulty Level Easy
Bit Bit Manipulation Bits

## 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
Sliding Window Technique

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.