# 119 - 461 汉明距离

## 题目

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

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

注意：

0 ≤ x, y < 231.

示例:

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

## 解答

感觉可以用异或，相同为0，相异为1。然后算一下有多少个1。

或者变成2进制，然后一个个算。

> <https://leetcode-cn.com/problems/hamming-distance/solution/yi-huo-hou-tong-ji-by-quincyz/>

我只想到用异或，但没想清楚该怎么统计。

这里是用和1与，来判断最右边那位是不是1，如果是就++。然后就右移一位。

```go
func hammingDistance(x int, y int) int {
    m := x ^ y
    count := 0
    for m > 0 {
        if m&1 > 0 {
            count++
        }
        m >>= 1
    }
    return count
}
```

> Runtime: 0 ms, faster than 100.00% of Go online submissions for Hamming Distance.
>
> Memory Usage: 2 MB, less than 100.00% of Go online submissions for Hamming Distance.

看到了一个更加简洁的方法：

> <https://leetcode-cn.com/problems/hamming-distance/solution/xian-jiang-liang-ge-shu-yi-huo-yun-suan-ran-hou-za/>

就把x和y覆盖掉，不用另外申请空间。

统计1的个数，也可以用`n&(n-1)`，更加高效

> <https://blog.csdn.net/u012965373/article/details/50592727>
>
> 简言之`n&(n-1)`可以把二进制最低位的1变成0

```go
func hammingDistance(x int, y int) int {
    y = x ^ y
    x = 0
    for y > 0 {
        y = y & (y - 1)
        x++
    }
    return x
}
```

> Runtime: 0 ms, faster than 100.00% of Go online submissions for Hamming Distance.
>
> Memory Usage: 2 MB, less than 100.00% of Go online submissions for Hamming Distance.

go:我实在是没法再快了

```javascript
var hammingDistance = function(x, y) {
  y = x ^ y
  x = 0
  while (y > 0) {
    y = y & (y - 1)
    x++
  }
  return x
};
```

> Runtime: 48 ms, faster than 93.66% of JavaScript online submissions for Hamming Distance.
>
> Memory Usage: 34 MB, less than 37.50% of JavaScript online submissions for Hamming Distance.

```python
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        y = x ^ y
        x = 0
        while y > 0:
            y = y & (y-1)
            x += 1
        return x
```

> Runtime: 48 ms, faster than 7.18% of Python3 online submissions for Hamming Distance.
>
> Memory Usage: 13.8 MB, less than 8.70% of Python3 online submissions for Hamming Distance.

python:我们不喜欢位运算。。

```python
class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return bin(x ^ y).count('1')
```

> Runtime: 40 ms, faster than 37.04% of Python3 online submissions for Hamming Distance.
>
> Memory Usage: 14 MB, less than 8.70% of Python3 online submissions for Hamming Distance.

python:但我们什么函数都有