An old dog learns code

[LeetCode 461] Hamming Distance

February 11, 2019


The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:  0x,y<231.\ 0 ≤ x, y < 2^{31}.

题目类型分析

题目要求汉明距离,即统计 2 个数在二进制形式下,不同二进制位的数量。
开始没有思路,只能判断出它不是考查数据结构、也不是某种算法的应用,先归入数学类应该是比较稳妥的。

解法

  1. 暴力求解法
    没有思路的情况下最容易想到暴力求解法,大概的流程如下:

    • 比较 x, y,假设 x 为二者中较大的一个,并以它为比较基准
    • 将 x, y 分别转换为二进制字符串,并将位数对齐
    • 从 x 的 LSB 开始,循环比较 y 对应位置的二进制位
    • 如果相同,计数不变;如果不同,计数+1
    • 循环结束,返回计数结果

    边界情况:如果 x, y 相等,那么直接返回 0;否则按照上述流程进行计算

    缺陷:存在大量的字符串拼接操作,也保存了完整的二进制字符串。考虑上述两个缺陷,改进的思路有了:1.不使用字符串,考虑直接使用数值进行比较 2. 不保存完整的二进制位,逐位比较完毕后直接丢弃,于是有了下面的解法。

  2. 改进一点的暴力求解法
    用“除二取余法”通过数值计算逐位获取二进制表示,同时完成比较,每次比较完毕后就丢弃结果。与上面提到的改进方向一致,大致流程如下:

    • x, y 分别对 2 取余数
    • 余数相同,则计数+1;否则不变
    • x, y 分别除以 2,不能整除则向下取整
    • 重复以上步骤,直至 x, y 均为 0 时,结束循环,返回计数

    边界情况: 同上

    缺陷:比方法 1 节省了字符串操作和存储,但仍然需要循环计算。

    能不能免去循环计算的过程呢?当然可以,请看下文。

  3. 利用数学原理求解
    查一下 wiki,汉明距离的标准算法就是 2 个数进行逻辑异或,结果中只包含二者不同的二进制位(也就是'1'),那么把结果中 1 的个数统计出来就是答案。(逻辑运算真是太美好了!)这个方法完整步骤太简单,就不写了。

    边界情况:同上

    缺陷: 继承了方法 2 的优点,不仅免去了循环计算,还更容易理解,重要结果一步就可以得到,应该是最优方案了吧。