02.Hamming Distance

发表于 更新于

给定两个数字，求这两个数的二进制数相应位不同的总数。

注意：
$0 \leq x, y < 2^{31}$

例子：

输入： x=1, y=4
输出: 2

解释：
1 (0 0 0 1)
4 (0 1 0 0)
^ ^
上面箭头指的位置相应两个数字的二进制位不一样，一共有2处。

##解法1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// javascript
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    let xor = x ^ y;
    let count = 0;
    while(xor !== 0) {
        count += xor & 1;
        xor = xor>>1;
    }
    return count;
};

首先通过异或操作得到一个值xor。
在循环里面判断有几个不一样的位置。
从最后一位开始判断，直到所有位置判断完成。

##解法2:

1
2
3
4
// javascript
var hammingDistance = function(x, y) {
    return (x ^ y).toString(2).replace(/0/g, '').length;
};

第一步同解法一。
第二步转换成操作字符串的操作。
删除’0’,随后判断字符串的长度，即不同位置数。

##解法3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//javascript
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    let xor = x ^ y;
    let count = 0;
    while(xor) {
        count++;
        xor &= xor-1;
    }
    return count;
};

其实这个问题可以简化成找出二进制数中有几个‘1’。比如异或结果是‘1010’，其中有2个‘1’表示hamming distance是2。

这段代码while循环可能一眼看上去发现自己懵逼了。其实xor &= xor-1;这个操作是移除一个’1‘。有几个就是移除几次。如果还懵逼，可以多调试几次。