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


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jaytp@qq.com

文章标题:02.Hamming Distance

字数:386

本文作者:ihugo

发布时间:2017-03-09, 14:40:47

最后更新:2022-03-11, 02:46:44

原始链接:http://ihugo.cc/2017/03/09/02-Hamming-Distance/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。