461. 汉明距离

# 题目

## 461. 汉明距离

[https://leetcode-cn.com/problems/hamming-distance/](https://leetcode-cn.com/problems/hamming-distance/)

两个整数之间的[汉明距离](https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E8%B7%9D%E7%A6%BB)指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 `x` 和 `y`，计算它们之间的汉明距离。

**注意：**
0 ≤ `x`, `y` < 231.

**示例:**

```
输入: x = 1, y = 4

输出: 2

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

上面的箭头指出了对应二进制位不同的位置。
```

# 题解

## 思路

异或之后，转二进制，求1的个数

## 代码

```javascript
/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var hammingDistance = function(x, y) {
    return (x ^ y).toString(2).split('').filter(i => i === '1').length;
};
```

## 官方

#### **移位实现位计数**

****思路及算法****

**在锻炼算法能力时，重复造轮子是不可避免的，也是应当的。因此读者们也需要尝试使用各种方法自己实现几个具有位计数功能的函数。本方法将使用位运算中移位的操作实现位计数功能。**

![](/media/202105/2021-05-27_215121.png)

具体地，记  s = x⊕y，我们可以不断地检查 s 的最低位，如果最低位为 11，那么令计数器加一，然后我们令 s 整体右移一位，这样 s 的最低位将被舍去，原本的次低位就变成了新的最低位。我们重复这个过程直到 s=0 为止。这样计数器中就累计了 s 的二进制表示中 11 的数量

```
var hammingDistance = function(x, y) {
    let s = x ^ y, ret = 0;
    while (s != 0) {
        ret += s & 1;
        s >>= 1;
    }
    return ret;
};
```