题目描述
两个整数间的汉明距离是指,这两个数字对应二进制位不同的位置的数目。
给定两个整数 x 和 y,计算它们间的汉明距离。
注意:
0 ≤ x, y < 2^31.
样例
示例:
输入: x = 1, y = 4
输出: 2
解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
上面的箭头指出了对应二进制位不同的位置。
思路
- 每次取出两个数的最后一位进行异或。若异或值为1,那么汉明距离就加1,否则x和y同时右移一位,进行下一轮的判断。当x和y均变为0时,循环结束。
- 取出最后一位的方法:x & 1,即可获得 x 的最后一位,y同理。
- 时间复杂度为O(n),n为x和y中位数的最大值,不超过32。
代码
class Solution {
public int hammingDistance(int x, int y) {
//记录总汉明距离
int cnt = 0;
while(true) {
//取出最后一位异或
int a = (x&1) ^ (y&1);
cnt += a;
x = x >> 1;
y = y >> 1;
if(x == 0 && y == 0)
break;
}
return cnt;
}
}