9.2 位运算基础问题

# 9.2 位运算基础问题

## [461. Hamming Distance](https://leetcode.com/problems/hamming-distance/)

### 题目描述

给定两个十进制数字，求它们二进制表示的汉明距离（Hamming distance，即不同位的个数）。

### 输入输出样例

输入是两个十进制整数，输出是一个十进制整数，表示两个输入数字的汉明距离。

```
Input: x = 1, y = 4
Output: 2
```

在这个样例中，1 的二进制是 0001，4 的二进制是 0100，一共有两位不同。

### 题解

对两个数进行按位异或操作，统计有多少个 1 即可。

```py
def hammingDistance(x: int, y: int) -> int:
    diff = x ^ y
    dist = 0
    while diff != 0:
        dist += diff & 1
        diff = diff >> 1
    return dist
```

## [190. Reverse Bits](https://leetcode.com/problems/reverse-bits/)

### 题目描述

给定一个十进制正整数，输出它在二进制下的翻转结果。

### 输入输出样例

输入和输出都是十进制正整数。

```
Input: 43261596 (00000010100101000001111010011100)
Output: 964176192 (00111001011110000010100101000000)
```

使用算术左移和右移，可以很轻易地实现二进制的翻转。

### 题解

```py
def reverseBits(n: int) -> int:
    m = 0
    for _ in range(32):
        m = m << 1
        m += n & 1
        n = n >> 1
    return m
```

## [136. Single Number](https://leetcode.com/problems/single-number/)

### 题目描述

给定一个整数数组，这个数组里只有一个数次出现了一次，其余数字出现了两次，求这个只出现一次的数字。

### 输入输出样例

输入是一个一维整数数组，输出是该数组内的一个整数。

```
Input: [4,1,2,1,2]
Output: 4
```

### 题解

我们可以利用 x ∧ x = 0 和 x ∧ 0 = x 的特点，将数组内所有的数字进行按位异或。出现两次的所有数字按位异或的结果是 0，0 与出现一次的数字异或可以得到这个数字本身。

```py
def singleNumber(nums: List[int]) -> int:
    single = 0
    for num in nums:
        single = single ^ num
    return single
```

这里我们也可以直接使用 reduce 函数：

```py
def singleNumber(nums: List[int]) -> int:
    return functools.reduce(lambda x, y: x ^ y, nums)
```