Leetcode - 461. Hamming Distance n&=(n-1) (C++)

1. 题目链接：https://leetcode.com/problems/hamming-distance/description/

2.思路

常规做法做完看到评论区一个非常有意思的做法。用了n&=(n-1)，这个地方的意思是，将最右边的1变成0。比方说：

最简单的例子：

原数字: 101011

n-1: 101010

n&(n-1)：101011&101010=101010

 

再看另一个例子：

原数字：10100

n-1: 10011

n&(n-1)：10100&10011 = 10000

 

最后一个极端情况：

原数字：10000

n-1：01111

n&(n-1)：10000&01111=00000

 

3.代码

（1）评论区的解法

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

（2）常规解法

class Solution {
public:
    int hammingDistance(int x, int y) {
        int n = x^y, hd = 0;
        while(n)
        {
            hd += (n % 2);
            n = n >> 1;
        }
        return hd;
    }
};