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;

    }

};

巴特西

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

最新文章

热门文章