My C++ solution using bit manipulation


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

  • 3
    J

    Could you explain how the loop works ? Thanks!


  • 21
    K

    @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.


  • 0
    J

    @kevin36 perfect thanks !


  • 2
    Z

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


  • 23

    @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


  • 0
    A

    remarkable code!


  • 0
    F
    This post is deleted!

  • 0
    X
    This post is deleted!

  • 0
    V

    @LCAR979 very clear explanation, thank you!


  • 0
    W

    Thank you ! Perfect!!!


  • 0
    P

    @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).


Log in to reply
 

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