13518219792
leetcode 461 汉明距离，难度：简单
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1：
输入：x = 1, y = 4
输出：2
解释：
1 (0 0 0 1)
4 (0 1 0 0)
对应二进制位不同的位置个数为2
示例 2：
输入：x = 3, y = 1
输出：1
提示：
0<= x, y<= 231 - 1
汉明距离应用汉明距离广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。
两个整数之间的汉明距离是对应位置上数字不同的位数。
解决此题，可以使用异或运算，当对应的二进制为不同时，输出为1，然后统计异或后1的个数。
统计二进制中1的个数，主要有3种方法：
下面分别介绍这3种算法
解法1：Brian Kernighan算法Brian Kernighan算法可以用于清除二进制数中最右侧的1。Brian Kernighan算法的做法是先将当前数减一，然后在与当前数进行按位与运算。
x=x&(x-1)示意图
x&(x-1)的结果变成了1110
利用此算法我们可以统计一个数字的二进制中的1的个数，即一比特数：
#includeusing namespace std;
int oneCounts(int num) {int ones = 0;
while (num >0) {num &= num - 1;
ones++;
}
return ones;
}
int main()
{int num = 23; // 1 0111
cout<< oneCounts(num)<< endl;
return 0;
} 对应的此题的解法
class Solution {public:
int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
while (s) {s &= s - 1;
ret++;
}
return ret;
}
};复杂度分析
时间复杂度：O(logC)，其中 C 是元素的数据范围;
空间复杂度：O(1)。
确实简单，简单的前提是得知道Brian Kernighan算法.
不知道Brian Kernighan算法也可以解决。
使用异或运算，记 s = x⊕y，我们可以不断地检查 s 的最低位，如果最低位为 1，那么令计数器加一，然后我们令 s 整体右移一位，这样 s 的最低位将被舍去，原本的次低位就变成了新的最低位。我们重复这个过程直到 s=0 为止。这样计数器中就累计了 s 的二进制表示中 1 的数量。
代码
class Solution {public:
int hammingDistance(int x, int y) {int s = x ^ y, ret = 0;
while (s) {ret += s & 1;
s >>= 1;
}
return ret;
}
};代码说明s&1, 如果最末位是1，那么s&1 = 1, ret += 1，否则ret += 0, 然后s右移一位。
解法3使用系统内置API: __builtin_popcount, 该函数可以统计二进制数中1的个数，但是仅在gcc/g++下可使用。
代码
#includeusing namespace std;
class Solution {public:
int hammingDistance(int x, int y) {return __builtin_popcount(x ^ y);
}
};
int main(){Solution s;
cout<< s.hammingDistance(1, 4)<< endl;
return 0;
} 虽然这是一道简单题，但是并不简单，leetcode没哪道题简单。
本文参考资料
（1）https://leetcode.cn/problems/hamming-distance
（2）https://zhuanlan.zhihu.com/p/498119781
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
