461. 汉明距离

问题

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x 和 y，计算它们之间的汉明距离。

例子

思路

• 使用方法2最佳

方法1：将两个数都变为等长的二进制字符串（短的在前面补零），比较相同的位数
方法2，将对两个数与或【同一位置，相同为1，不同为0】，把得到的数转换为二进制补码字符串，遍历1的个数
方法3，把对两个数的比较，变为与第三个数的比较
答案

//方法1：将两个数都变为等长的二进制字符串（短的在前面补零），比较相同的位数
public int hammingDistance(int x, int y) {

    int count = 0;
    String s1 = Integer.toBinaryString(x);
    String s2 = Integer.toBinaryString(y);
    int n = Math.abs(s1.length()-s2.length());
    if (s1.length()<s2.length()) {
        for(int i=0; i<n; i++) s1 = "0"+s1;
    }else {
        for(int i=0; i<n; i++) s2 = "0"+s2;
    }
    int count = 0;
    for(int i=0;i<s1.length();i++) 
        if(s1.charAt(i)!=s2.charAt(i)) count++;
    
    return count;
}
//方法2，将对两个数与或【同一位置，相同为1，不同为0】，把得到的数转换为二进制补码字符串，遍历1的个数
public int hammingDistance(int x, int y) {
    int t = x^y;
    int count = 0;
    String s = Integer.toBinaryString(t);
    for (int i=0; i<s.length(); i++) {
        if (s.charAt(i)=='1') count++;
    }
    return count;
}
//方法3，把对两个数的比较，变为与第三个数的比较
public int hammingDistance(int x, int y) {
    int count=0;
    int last_x=-1,last_y=-1;
    while(x>0 || y>0){//x==0且y==0是结束
        //判断最后一个是否为1
        last_x = x&1;
        last_y = y&1;
        if (last_x!=last_y) count++;
        //把最后一位去掉
        x=x>>1;
        y=y>>1;
    }
    return count;
}

	#方法2
    def hammingDistance(self, x: int, y: int) -> int:
        t = x^y
        s = bin(t)[2:]
        count=0
        for i in range(len(s)):
            if s[i]=='1': count+=1
        return count