# My C++ solution using bit manipulation

• ``````class Solution {
public:
int hammingDistance(int x, int y) {
int dist = 0, n = x ^ y;
while (n) {
++dist;
n &= n - 1;
}
return dist;
}
};
``````

• Could you explain how the loop works ? Thanks!

• @jonvasquez1
So the while works by turning off the right most bit in n in each iteration, the details are as follows.

the "while(n)" par is equivalent to while there is a bit set go into the loop

when were in the loop the "++dist" just counts how may bits we have turned off(set to 0) so far

the "n &= n-1" turns off(set to 0) the right most 1 bit, you can see this by just trying a few examples.

so where we exit the loop we know that n must be zero and hence dist will contain the number of bits set to one in x^y.

That's how the loop works.

• @kevin36 perfect thanks !

• @jonvasquez1 for any binary number n, n&=n-1 can change the last 1 to 0.

• @jonvasquez1 Considering this example. Let's say `n = 10101`, and `dist = 0` asccording to above code of @pengr7.

• Before we go into the `while` loop. `n = 10101, dist = 0`
• Loop 1. `dist = 1, n =10101 & 10100 = 10100`
• Loop 2. `dist = 2, n =10100 & 10011 = 10000`
• Loop 3. `dist = 3, n =10000 & (0)1111 = 0`
• Loop ends. `dist = 3`

The change of `n` :

• `10101`
• `10100`
• `10000`
• `00000`

Conclusion: `n & (n-1)` converts the right most `1` to `0` .
This is the key idea solving the problem. By counting how many times we can perform this operation, we know how many `1` exists in the binary representation of `n`

• remarkable code!

• This post is deleted!

• This post is deleted!

• @LCAR979 very clear explanation, thank you!

• Thank you ! Perfect!!!

• @pengr7 Your solution is very fast and performant, I like it a lot!!! In my original solution I used bitwise shift operator and counted 1s when they became LSB. Which turns out to be the slowest solution of all because number of operations is quite large (when your numbers are big).

• @LCAR979 Thanks for your detailed explanation!

• This post is deleted!

• Nice work! Cool technique for counting lit bits

• @pengr7 666,xue xi le

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