LeetCode算法题-Hamming Distance（Java实现）
这是悦乐书的第237次更新，第250篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第104题（顺位题号是461）。两个整数之间的汉明距离是相应位不同的位置数。给定两个整数x和y，计算汉明距离。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。注意：0≤x，y <2^31。
例如：
输入：x = 1，y = 4
输出：2
说明：
1（0 0 0 1）
4（0 1 0 0）
↑ ↑
上述箭头指向相应位不同的位置。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
因为x和y都是正数，所以不用考虑反码、补码的事情，所以可以使用字符串操作。如果转成二进制字符串后，两字符串的长度不相等，所以要先把短的字符串前面补齐0，然后再使用循环，依次判断两字符串的字符，如果字符不同就记数加1，最后返回。
public int hammingDistance(int x, int y) {
String str = Integer.toBinaryString(x);
String str2 = Integer.toBinaryString(y);
int count = 0;
if (str.length() != str2.length()) {
if (str.length() < str2.length()) {
while (str.length() != str2.length()) {
str = "0" + str;
}
} else {
while (str.length() != str2.length()) {
str2 = "0" + str2;
}
}
}
for (int i=0; i<str.length(); i++) {
if (str.charAt(i) != str2.charAt(i)) {
count++;
}
}
return count;
}03 第二种解法
从题目的例子中，我们看出1和4所表示的二进制数在做异或运算后是5，转成二进制数就是101，也就是说，其中两个1就是1和4不同的位，所以我们可以借助异或运算。
异或（^）运算的规则是两边的对应位不同时就取1，使用异或计算得到对应的整数后，我们需要计算其中1位的个数，这就和之前有道题类似了，可以借鉴那边的解法。
public int hammingDistance2(int x, int y) {
int result = x^y;
String str = Integer.toBinaryString(result);
int count = 0;
for (int i=0; i<str.length(); i++) {
if (str.charAt(i) == 49) {
count++;
}
}
return count;
}04 第三种解法
同样是借助异或运算，在计算二进制数1位的个数时，使用的是与运算，具体的思路可以参照之前的一篇。
public int hammingDistance3(int x, int y) {
int result = x^y;
int count = 0;
while (result != 0) {
count++;
result = result & (result - 1);
}
return count;
}05 第四种解法
直接使用异或运算，然后借助包装类Integer的bitCount方法，返回二进制数中1位的个数。
public int hammingDistance4(int x, int y) {
return Integer.bitCount(x^y);
}06 小结
算法专题目前已日更超过三个月，算法题文章104+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
相关题目：
https://www.cnblogs.com/xiaochuan94/p/10036146.html
