02.Hamming Distance

作者 iHugo 日期 2017-03-09
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:

// 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:

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

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

##解法3:

//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‘。有几个就是移除几次。如果还懵逼,可以多调试几次。