Jack N @ GitHub

Full stack engineer, focus on: Angular/React, node.js/.Net

0%

算法 - 计算汉明距离

算法 - 计算汉明距离

1. 题目

给出两个整数 x 和 y,计算它们之间的汉明距离。

汉明距离是使用在数据传输差错控制编码里面的,汉明距离是一个概念,它表示两个(相同长度)字对应位不同的数量,我们以d(x,y)表示两个字x,y之间的汉明距离。对两个字符串进行异或运算,并统计结果为1的个数,那么这个数就是汉明距离。
示例:

  • 输入: x = 1, y = 8
  • 输出: 2
  • 解释:
    1
    2
    3
    1   (0 0 0 1)
    8 (1 0 0 0)
    ↑ ↑
    上面的箭头指出了对应二进制位不同的位置。

2. 代码

2.1. C#

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int HammingDistance(int x, int y) {
var n = x ^ y;

// 计算1的个数
var counter = 0;
while(n>0){
n = n & (n-1);
counter ++;
}
return counter;
}
}

2.2. Javascript

1
2
3
4
5
6
7
8
9
var hammingDistance = function(x, y) {
let n = x^y;
let counter = 0;
while(n){
counter ++;
n = n & (n-1);
}
return counter;
};

3. 另:计算二进制数字中1的个数

一个整数减去1,再和原整数做与运算,会把该整数最右边一个1变成0。
因此,一个整数的二进制有多少个1,就可以进行多少次这样的操作。

1
2
3
4
5
let counter = 0;
while(n){
counter ++;
n = n & (n-1);
}

算法 - 计算汉明距离