LeetCode——汉明距离

题目描述

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

上面的箭头指出了对应二进制位不同的位置。

一、CPP

1. 异或法：

解题思路:对x和y进行异或运算，得出的数换算为二进制，其中1的个数就是x与y对应位置不同的数目。
时间复杂度:
空间复杂度:

class Solution {
public:
    int hammingDistance(int x, int y) {

        int count = 0;
        int b;
        int a = x ^ y;

        while(a){
            b = a % 2;
            a /= 2;
            if(b){
                ++count;
            }
        }
        return count;        
    }
};

二、Java

class Solution {
    public int hammingDistance(int x, int y) {

        int count = 0;
        int b;
        int a = x ^ y;

        while(a!=0){
            b = a % 2;
            a /= 2;
            if(b==1){
                ++count;
            }
        }
        return count; 
        
    }
}

//另一简单解法
class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

三、Python

class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        a = x ^ y
        count = 0
        while a:
            b = a % 2
            a //= 2
            if b:
                count += 1
        return count

//另一简单解法
class Solution(object):
    def hammingDistance(self, x, y):
        """
        :type x: int
        :type y: int
        :rtype: int
        """
        return bin(x ^ y).count('1')     

四、各语言及算法时间复杂度