汉明距离（位运算，清晰图解）

程序员小熊

发布于 2021-05-28 12:52:19

1.1K0

发布于 2021-05-28 12:52:19

文章被收录于专栏：程序员小熊带你学算法

温馨提示，本文共 998 字，阅读完成大概需要 3 分钟。

题目

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

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

注意：0 ≤ x, y < 2^31.

示例:

解题思路

要找出两个整数对应二进制位不同的位置的数目，对 位运算 有所了解的童鞋，应该会很自然地想到位运算中的 按位异或，通过将两个整数对应二进制位 按位异或（同一位置，元素相同异或得 0 或者得 1） 找到其二进制不同的位置，找到之后，只需要统计异或的结果中 1 的个数即可。

举栗

以示例为栗，如下图示：

元素值及其对应的二进制

异或之后的结果

统计整数的二进制表达中 1 的个数

以上面 x ^ y 的结果为栗，统计 x ^ y 中 1 的个数

cnt 记录 x ^ y 中 1 的个数

方法一 ：通过不断右移获取末尾位统计二进制中 1 的个数

第一次

x ^ y 右移一位

右移末尾为 0 继续右移

第二次

x ^ y 继续右移一位

此时 x ^ y == 0，无需再右移。

方法二 ：通过 n & (n - 1) 统计二进制中 1 的个数

还是以上面的 x ^ y 的结果为栗，统计 x ^ y 中 1 的个数，假设 n = x ^ y

第一次

第二次

此时 n & (n - 1) == 0，统计完成。

Show me the Code

c 语言

int hammingDistance(int x, int y){
  int cnt = 0;
  int z = x ^ y;
  while (z != 0) {
    cnt += z & 1;
    z = z>>1;
  }
  
  return cnt;
}

c++

int hammingDistance(int x, int y) {
    int cnt = 0;
    int z = x ^ y;
    while (z != 0) {
        cnt++;
        z &= (z - 1);
    }

    return cnt;
}

python3

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        cnt, z = 0, x ^ y
        while z != 0:
            cnt += 1
            z = z & (z - 1)
            
        return cnt

golang

func hammingDistance(x int, y int) int {
    cnt, z := 0, x ^ y
    for z != 0 {
        cnt++
        z &= z - 1
    }
    
    return cnt
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-31，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自程序员小熊微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度