# C# - Simple solution

• Do XOR between the numbers which then gives the difference bits as '1'
• Calculate those difference no.of bits by bit-END operation on preceding numbers until it is zero
...............
public int HammingDistance(int x, int y) {
int z = x ^ y;
int n = 0;
while(z > 0)
{
z = z & (z-1);
++n;
}
return n;
}
...............

• Such great solution it is.
I just do not understand how it works so well since I have sow it.
Can you give me a way to understand it?

• This post is deleted!

• // XOR returns no.of bits that are not same at corresponding positions
// 2- 0010 and 6 - 0110. Both integers differ at positions (left to right) 3. 2 ^ 6 = 0010 ^ 0110 = 0100
// You may notice the 1 in the result.
// Now if we could calculate all those 1's from the result above we get the hamming distance

// Any two consecutive numbers when written in base2 always differ by either
// only one bit or differ by all bits - Ex 10000 (16) and 1111(15) differ by all bits
// (ignore leading zeros) and 1111 (15) 1110(14) differ by 1.Doing & operation on the result
//continuously will exhaust all 1s and leads to zero. If we want to calculate number of bits in
//4...0100(4) & 0011(3) becomes zero by then n is incremented by 1 which is our answer

• @krishnacs

It's amazing that & operation can exhaust one '1' once a time. I've learned a lot from this.
I'm new comer to Leet Code and this is the first question I learned.
Thank you again.

• @krishnacs XOR does NOT return no.of bits that are not same at corresponding positions. Try it with 7 ^ 8

• @Aevil1 Hi Aevil1,
XOR returns no.of bits that are not same.

0 ^ 0 - 0
0 ^ 1 - 1
1 ^ 0 - 1
1 ^ 1 - 0

`````` 7   --> 0 1 1 1
8   --> 1 0 0 0
----------------
7^8 -->1 1 1 1
``````

You may notice 7 and 8 have 4 bits different. When you do AND operation on this result until it is zero, we get the count of set bits.

• @krishnacs : what about difference between 96 (1100000) and 95 (1011111)? It has only 6 differences. can you help me understand it?

• @xXx This is Brian Kernighanâ€™s Algorithm. Google it and there are plenty good explanation articles out there.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.