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

时间:2023-01-08 15:31:48

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;
    }
};