LeetCode偶尔一题 —— 461. 汉明距离

原题地址:https://leetcode-cn.com/problems/hamming-distance/
repo 地址: https://github.com/pigpigever/leetcode-js-tonychen

题目剖析🧐

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数 x 和 y,计算它们之间的汉明距离。

比如说存在这样两个二进制数值:

  • 001
  • 100

它们之间的汉明距离就是 2,我们要求的就是两个二进制数值中位数不一样的地方,比如你是 1 他是 0,那么汉明距离就 +1

前置知识📖

异或运算是相对基础的知识,但是由于在平时的开发中几乎不会用到,难免生疏。这里简单罗列下常见的异或运算:

  • & : 按二进制位进行 与运算,相同位同时为 1 时结果为 1,否则为 0
  • | : 按二进制位进行 或运算,相同位存在 01 时结果为 1,否则为 1
  • ^ : 按二进制位进行 异或运算,相同位相同时为 0,否则为 1
  • >> : 右移运算是将一个二进制位的操作数按指定移动的位数向右移动,移出位被丢弃,左边移出的空位或者一律补 0
  • << : 左移运算是将一个二进制位的操作数按指定移动的位数向左移位,移出位被丢弃,右边的空位一律补 0

梳理逻辑💡

思路其实很简单,如下:

  • 遍历两个数值,位数不相同那么 +1

示例代码🌰

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
* @param {number} x
* @param {number} y
* @return {number}
*/
var hammingDistance = function(x, y) {
let ans = 0
while (x !== 0 || y !== 0) {
if ((x & 1) !== (y & 1)) {
ans++
}
x >>= 1
y >>= 1
}
return ans
};