# 二进制
## 常见二进制操作
### 基本操作
a=0^a=a^0
0=a^a
由上面两个推导出：a=a^b^b
### 交换两个数
a=a^b
b=a^b
a=a^b
### 移除最后一个 1
a=n&(n-1)
### 获取最后一个 1
diff=(n&(n-1))^n
## 常见题目
[single-number](https://leetcode-cn.com/problems/single-number/)
> 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
```c++
int singleNumber(vector& nums) {
// 10 ^10 == 00
// 两个数异或就变成0
auto result = 0;
for (const auto &num : nums) {
result ^= num;
}
return result;
}
```
[single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)
> 给定一个**非空**整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
```c++
// 思路：每一位，统计有多少个1，除以3取余数
// 出现三次的，取余数为0，被过滤掉，剩下的都是只出现一次的那个数
int singleNumber(vector& nums) {
auto ret = 0;
for (int i = 0; i < 32; ++i) {
auto sumOne = 0;
for (const auto &item : nums) {
sumOne += (item >> i) & 1;
}
ret ^= (sumOne % 3) << i;
}
return ret;
}
```
[single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)
> 给定一个整数数组 `nums`，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
```c++
vector singleNumber(vector& nums) {
auto diff = 0;
// 按位与，出现两次的数会被剔除掉
for (const auto &item : nums) {
diff ^= item;
}
vector result(2);
// 只出现一次的两个数不想等，则其异或的结果必然至少有一位为 1
// 找到最后一个 '1'
diff &= (-diff);
// 再按该位上的值为1还是为0将所有的数分成两组进行异或把两个数分开
for (const auto &num : nums) {
if ((diff & num) == 0) {
result[0] ^= num;
} else {
result[1] ^= num;
}
}
return result;
}
```
> 关于 x & (-x)
> 在计算机系统中，数值一律用补码来表示和存储
> 一个正数 x 与其相反数 -x，只有一位同时为 '1'，并且总为 x 中的最后一位 '1'
> 正数的补码与原码相同
> 负数的补码，将其原码除符号位外的所有位取反后加1
> 10和-10用8位表示为：
> 10: 0000 1010
> -10: 1111 1010
> 因此，x & (-x) 可用于求出x中最后一个'1'
[number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)
> 编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为[汉明重量](https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F)）。
```c++
int hammingWeight(int n) {
auto ret = 0;
while (n != 0) {
n = n & (n - 1);
++ret;
}
return ret;
}
```
[counting-bits](https://leetcode-cn.com/problems/counting-bits/)
> 给定一个非负整数 **num**。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。
```c++
vector countBits(int num) {
vector ret(num+1);
for (int i = 0; i <= num; ++i) {
ret[i] = hammingWeight(i);
}
return ret;
}
int hammingWeight(int n) {
auto ret = 0;
while (n != 0) {
n = n & (n - 1);
++ret;
}
return ret;
}
```
另外一种动态规划解法
```c++
vector countBits(int num) {
vector ret(num + 1);
for (int i = 1; i <= num; ++i) {
// 对于 i，其二进制1的个数 = 移除其最后一个1剩余的1的个数 + 1
// i & (i - 1)移除最后一个1
ret[i] = ret[i & (i - 1)] + 1;
}
return ret;
}
```
[reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)
> 颠倒给定的 32 位无符号整数的二进制位。
思路：依次颠倒即可
```c++
uint32_t reverseBits(uint32_t n) {
uint32_t ret = 0; // 记得初始化，否则通不过
auto pow = 31;
while(n != 0) {
// 取最后一位进行左移
ret += (n & 1) << pow;
n >>= 1;
--pow;
}
return ret;
}
```
[bitwise-and-of-numbers-range](https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/)
> 给定范围 [m, n]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。
```c++
/*
* 思路：
* 只要有一位不同时位1，则按位与结果为0
* 因此，从m和n最左边一个不同时为1的位起，其右边的位都将被剔除，如：
* m = 5 0101
* n = 15 1111
* 后面2位最终会变为0
* 所以，掐头去尾取中间（左边起第二个1）么？
* 不，n再大也没用，m跟n最左边的1必须在同一位，否则结果直接为0
* 毕竟终归是会有一个中间的数，10000，按位与完，m就没了
*
* 所以，m、n同时右移，直到二者相等（剩下最左边的若干个1，或者为0）
* 再进行左移
*/
int rangeBitwiseAnd(int m, int n) {
auto zeroNum = 0;
while (m != n) {
m >>= 1;
n >>= 1;
++zeroNum;
}
return m << zeroNum;
}
```
## 练习
- [ ] [single-number](https://leetcode-cn.com/problems/single-number/)
- [ ] [single-number-ii](https://leetcode-cn.com/problems/single-number-ii/)
- [ ] [single-number-iii](https://leetcode-cn.com/problems/single-number-iii/)
- [ ] [number-of-1-bits](https://leetcode-cn.com/problems/number-of-1-bits/)
- [ ] [counting-bits](https://leetcode-cn.com/problems/counting-bits/)
- [ ] [reverse-bits](https://leetcode-cn.com/problems/reverse-bits/)