hamming-distance

Hamming Distance – LeetCode 461

Problem

Description

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
$0 ≤ x, y < 2^{31}.$

Answer

Original

Code

class Solution {
public:
    int hammingDistance(int x, int y) {
        long long z = x ^ y;
        y = 0;
        while(z){
            z ^= (((z - 1) ^ z) + 1) >> 1;
            ++y;
        }
        return y;
    }
};

思路

直接亦或然后数设置的位数，这里用位操作。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$5$ ms，排名$76.27\%$

Better

思路

使用bitset数数。时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$4$ ms，排名$76.27\%$

Code

class Solution {
public:
    int hammingDistance(int x, int y) {
        bitset<32> z(x^y);
        return z.count();
    }
};