Bit_Manipulation.md

<span id = "00"></span>
## 基础
 - [389. Find the Difference](#389-find-the-difference)
 - [136. Single Number](#136-single-number)
 - [137. Single Number II](#137-single-number-ii)
 - [318    Maximum Product of Word Lengths]
## 很少考            
 - [393    UTF-8 Validation]
 - [201. Bitwise AND of Numbers Range](#201-bitwise-and-of-numbers-range)
 - [371. Sum of Two Integers](#371-sum-of-two-integers)
 - [338. Counting Bits](#338-counting-bits)
 - [89    Gray Code]
 - [268. Missing Number](#268-missing-number)
 - [191. Number of 1 Bits](#191-number-of-1-bits)
 - [190. Reverse Bits](#190-reverse-bits)
 - [260    Single Number III]


## 389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

给定两个字符串s和t，它们只包含小写字母。 字符串t由随机混洗字符串s生成，然后在随机位置再添加一个字母。 找到t中添加的字母

**Example**

```
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.
```

---

### Python Solution
**分析：** 将 s 中字符转成它的 ASCII 码，然后进行异或，得到的结果与同样处理的 t 进行异或，最后的结果既是 t 中多出来的值的 ASCII 码，恢复成字符即可。

```python
from functools import reduce
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(reduce(int.__xor__, map(ord, s+t)))
```

**Solution2:** 这样的话更好理解一点

```python
class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return chr(sum(map(ord, t)) - sum(map(ord, s)))
```

[返回目录](#00)


## 136. Single Number

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

给定一个非空的整数数组，除了一个元素外，每个元素都会出现两次。找一个单一的。

**Example**

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

---

### Python Solution
**分析：** 很经典的一个位运算异或的题目。利用异或的性质，可以将重复2次的数字去除，所以遍历一遍后剩下的就是单次出现的数字。

```python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res ^= i
        return res
```

**reduce 的一个用法** 这里我们同样可以通过 reduce() 函数来完成，只是提供思路，但效率没有上面的高（涉及导入包、调用函数之类）

```python
from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(int.__xor__, nums)
```

[返回目录](#00)

## 137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

给定一个非空的整数数组，每个元素出现三次，除了一次，恰好出现一次。 找到那一个。

注意：您的算法应具有线性运行时复杂度。 您可以在不使用额外内存的情况下实现它吗？

**Example**

```
Input: [0,1,0,1,0,1,99]
Output: 99
```

---

### Python Solution
**分析：** 两种做法：1. 比较容易想到。遍历位数，如果所有数字在这位上的总和不是3的倍数，那么单次出现的数字在这一位一定有值，逐位拼凑出来这个数字 2. 这个解法比较炫酷，需要对位运算比较了解，面试不易想出。如果你想写这种解法，请确定你一定可以每一步都和面试官沟通清楚。

```python
class Solution:
    def singleNumber(self, nums):
        ans = 0
        for i in range(32):
            cnt = 0
            for n in nums:
                if (n >> i) & 1:
                    cnt += 1
            if cnt % 3:
                ans |= 1 << i
        return ans if ans < 2**31 else ans - 2**32
```

```python
class Solution:
    def singleNumber(self, nums):
        a = b = 0
        for n in nums:
            a = (a ^ n) & ~b
            b = (b ^ n) & ~a
        return a
```

[返回目录](#00)

## 201. Bitwise AND of Numbers Range

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

给定范围[m，n]，其中0 <= m <= n <= 2147483647，返回此范围内所有数字的按位AND，包括端值。

**Example**

```
Input: [5,7]
Output: 4
```

---

### Python Solution
**分析：** 只要找到两端的公共部分即可。

```python
class Solution:
    def rangeBitwiseAnd(self, m: int, n: int) -> int:
        shift = 0
        while m and m != n:   # NOTE: break when m == 0
            m >>= 1
            n >>= 1
            shift += 1
        return m << shift
```

[返回目录](#00)

## 371. Sum of Two Integers

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

计算两个整数a和b的总和，但不允许使用运算符+和 - 。

**Example**

```
Input: a = -2, b = 3
Output: 1
```

---

### Python Solution
**分析：** 通过位运算来实现。异或是两者不同的位，与运算是两者相同需要进位的位，将这两个相加即可完成两个数的加法。同样异或结果和与运算结果也是通过这样来完成相加的。因为 Python 没有整型溢出，所以需要规定个范围掩码，当 num2 超过 mask 时，num1 也要和 mask 做 与 。

```python
class Solution:
    def Add(self, num1, num2):
        mask = 0xffffffff
        while num2 & mask:
            num1, num2 = num1 ^ num2, (num1 & num2) << 1
        return num1 & mask if num2 > mask else num1
```

[返回目录](#00)

## 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

给定一个非负整数num。对于0≤i≤num范围内的每个数字i，以二进制表示形式计算1的数目，并将它们作为数组返回。

**Example**

```
Example 1:

Input: 2
Output: [0,1,1]

Example 2:

Input: 5
Output: [0,1,1,2,1,2]
```

---

### Python Solution
**分析：** 第一种解法有点类似于找规律但是可以将大数分解为小的部分进行求解。第二种解法就是根据数的二进制表示了。

```python
class Solution:
    def countBits(self, num: int) -> List[int]:
      res = [0]
      while len(res) <= num:
          res += [i+1 for i in res]
      return res[:num+1]
```

```python
class Solution:
    def countBits(self, num: int) -> List[int]:
        ans = [0] * (num+1)
        for i in range(1,num+1):
            ans[i] = ans[i & (i-1)] + 1
        return ans
```

[返回目录](#00)

## 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

给定一个数组，该数组包含从0、1、2，...，n中获取的n个不同的数字，请找到该数组中缺少的一个。

**Example**

```
Example 1:

Input: [3,0,1]
Output: 2

Example 2:

Input: [9,6,4,2,3,5,7,0,1]
Output: 8
```

---

### Python Solution
**分析：** 第一种解法为异或的用法。第二种解法十分简单：数列求和。

```python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)
        for i, v in enumerate(nums):
            res ^= i ^ v
        return res
```

```python
class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        res = len(nums)
        for i, v in enumerate(nums):
            res += i - v
        return res
```

[返回目录](#00)

## 191. Number of 1 Bits

Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

编写一个函数，该函数采用无符号整数并返回其具有的'1'位的数量（也称为汉明权重）。

**Example**

```
Example 1:

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Example 2:

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
```

---

### Python Solution
**分析：** 第一种解法为位运算，难点在于怎么快速取到最后一位为1。第二种解法用的库函数

```python
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            res += 1
            n &= (n - 1)
        return res
```

```python
class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count("1")
```

[返回目录](#00)

## 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

给定的32位无符号整数的反向位。

**Example**

```
Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
```

---

### Python Solution
**分析：** 位运算

```python
class Solution:
    def reverseBits(self, n: int) -> int:
        res = 0
        for _ in range(32):
            res = (res << 1) | (n & 1)
            n >>= 1
        return res
```

[返回目录](#00)