class Solution {
public:
    int hammingDistance(int x, int y) {
        int result = 0;
        int n = x^y; // binary number로 만들어 준다.
        while(n)
        {
            n &= (n-1);
            result ++;
        }
        return result;


    }
};

Hi, I spent 4 hours thinking how it works. It’s Brian Kernighan’s algorithm.

1. After we got XOR (n = x ^ y) which gives us a binary where count of 1’s (set bits) is exactly the number of different bits in the given pair of numbers, we only need to count those 1’s (set bits). [0]1[1]00 ^ [1]1[0]00 = [1]0[1]00

2. LOOP STARTS: with (n-1) we will have all the bits flipped after the rightmost set bit(1) of n (including the rightmost set bit) and leave bits to the left untouched. Consider: 10[100] - 00[001] = 10[011] or 111010[1]- 000000[1]= 111010[0]

3. now that we have ‘inverted’ the rightmost set bit, we can easily convert it and all the bits after it to 0 by doing n &= n -1; 10[100]& 10[011]= 10[000]

count this loop (++dist)

while loop breaks when we do operation 2 and 3 for the leftmost set bit (leftmost 1) because then n turns into 0. LOOP ENDS.

return dist.

that’s it :)

link explaining the algo: https://www.techiedelight.com/brian-kernighans-algorithm-count-set-bits-integer/