Python编程题37--汉明距离

2021/12/18 17:20:19

本文主要是介绍Python编程题37--汉明距离,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目

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

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

例如:

给定两个整数:x = 1, y = 4,返回结果:2

解释:
1 = (0 0 0 1)
4 = (0 1 0 0)

可以看出 1 和 4 对应二进制位不同的位置的数目有 2 个。

说明:0 ≤ x, y ≤ 2^31 - 1

实现思路1

  • 使用 二进制 的方式来实现
  • 通过 bin() 函数,先把 x 和 y 都转换为二进制数(字符串形式,如整数 10 转换为二进制后为 0b1010,开头的0b表示是二进制)
  • 根据 x 和 y 的范围说明,可以知道其最大值转换为二进制数后是31位,所以可通过 zfill() 函数,继续把 x, y 处理为32位的二进制数,不足32位就用 0 补足
  • 用 res 表示两个数字对应二进制位不同的位置的数目
  • 遍历转换后的 x 或 y,对比二进制位不同的位置,如果不相同则加 1

代码实现1

def hammingDistance(x, y):
    res = 0
    # bin()方法 转为二进制数,zfill() 方法返回指定长度的字符串
    tmp_x, tmp_y = bin(x)[2:].zfill(32), bin(y)[2:].zfill(32)
    for i in range(len(tmp_x)):
        if tmp_x[i] != tmp_y[i]:
            res += 1
    return res

实现思路2

  • 使用 异或运算 + 二进制 的方式来实现
  • 先对 x 和 y 进行异或运算,异或运算时,其实也是转化为二进制后按位比较(相同位的值为0,不同为1)
  • 接着把异或后的结果,通过 bin() 函数转换为字符串形式的二进制数
  • 最后通过 count() 函数 统计出转换后的二进制数中有多少个 1 即可

在二进制的异或运算中,例如a=12,b=7,那么a异或b的结果c计算如下:

a = 0 0 0 0 1 1 0 0
b = 0 0 0 0 0 1 1 1
c = 0 0 0 0 1 0 1 1 (相同位的值为0,不同为1)

代码实现2

def hammingDistance(x, y):
    return bin(x ^ y).count("1")

实现思路3

  • 不使用内置的二进制函数,仅使用 位运算符 的方式实现
  • 先对 x 和 y 进行异或运算,用 res 表示异或结果,接着需统计 res 对应的二进制数中有多少个 1 ,用 count 来表示,其默认值为 0
  • while循环,当 res 大于0时,对 res 和 1 进行 & 与运算,其目的是检查 res 对应二进制中的最低位是否是否为 1 ,如果为 1 则令 count 加 1
  • 每次循环,最后都需要把 res 通过 >> 运算符 整体右移一位,这样一来, res 对应二进制中的最低位就会被舍弃,其次低位在右移后自然就变为了新的最低位
  • 重复以上过程,直到 res=0 时退出循环,最终得到的 count 就统计出了原 res 对应二进制中 1 的个数

& 按位与运算符:参与运算的两个二进制数, 如果两个相应位都为1, 则该位的结果为1, 否则为0;
>> 右移动运算符:如 i >> 1,表示将 i 对应的二进制数整体右移一位,其实也就相当于 i // 2

代码实现3

def hammingDistance(x, y):
    res, count = x ^ y, 0
    while res:
        count += res & 1
        res >>= 1
    return count

更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)



这篇关于Python编程题37--汉明距离的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程