每天进步一点点🤏

汉明距离

  • 950 字

汉明距离

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目
给你两个整数 x 和 y,计算并返回它们之间的汉明距离

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

示例 2：
输入：x = 3, y = 1
输出：1

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
思路:
计算两个二进制位不同的数目,使用^位异或,相同的位返回0不同返回1,直接数1的数量,就是结果

代码:
/**
 * @param Integer $x
 * @param Integer $y
 *
 * @return Integer
 */
function hammingDistance($x, $y)
{
    $n = $x ^ $y;

    $num = 0;
    while ($n > 0) {
        $n = intdiv($n, 2);
        if ($n % 2 === 1) {
            $num++;
        }
    }

    return $num;
}

进阶代码: 只遍历1
/**
 * @param Integer $x
 * @param Integer $y
 *
 * @return Integer
 */
function hammingDistance($x, $y)
{
    $n = $x ^ $y;

    $num = 0;
    while ($n > 0) {
        // 一个数与这个数-1,进行位与运算,得到的结果=这个数移除最右边的1
        // 每次移除一个1直到$n==0为止
        $n = $n & ($n - 1);
        $num++;
    }

    return $num;
}