海明距离 | Java刷题打卡

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

一、题目描述：

二、思路分析：

今天给大家分享的是一道easy题目，求两个整数的汉明距离。所谓汉明距离指的是两个数字对应的二进制位不同的位置的数目。

直接按位遍历求不同

第一个比较直观的思路就是直接按位比较两个整数的二进制位。因为是32位int，直接位移32次，每次求出最低位的数字，然后对最低位的数字进行异或，得到1就表示这一位不同。遍历完成后就可以得到结果。

function hammingDistance($x, $y) {
        $ret = 0;
        for ($i = 0; $i < 32; $i++) {
            $x1 = ($x >> $i) & 1;
            $y1 = ($y >> $i) & 1;
            if ($x1 ^ $y1) {
                $ret++;
            }
        }

        return $ret;
    }
复制代码

另一种思路

另一种思路就是先求出两个数字的异或结果，然后求出这个结果中数字1的数目，即为汉明距离。
求数字的1的数目建议背诵。

class Solution {

    /**
     * @param Integer $x
     * @param Integer $y
     * @return Integer
     */
    function hammingDistance($x, $y) {
        $temp = $x ^ $y;
        $res = 0;
        while($temp) {
            $temp = $temp & ($temp-1);
            $res++;
        }
        return $res;
    }
}
复制代码

三、AC 代码：

四、总结：

今天的题目比较简单，考察位运算的，其中用到的求一个二进制表示中位1的个数比较常见，建议直接熟记相关代码。