目录
1.2 给一个数n，确定它的二进制表示中的第x位是0还是1？
1.位运算：常规运算总结：
在讲解今天的算法题之前，咱们先来讲解一下这个位运算的常规运算，以便于咱们后面的使用。（这个运算其实挺重要的，关系到咱们后面习题的做题的速度）
1.1 基础的位运算：
<< >> ~
还有三个比较重要的，并且比较容易混乱的：&：按位与。|：按位或。^：按位异或。好，那么这三个的功能该怎么记呢？&：有0就是0，无0为1.（&中都是0，所以记为有0则是0）|:有1就是1.^:有两种记忆方法：1.相同为0，相异为1. 2.无进位想加（就是进位的时候，不往前进一位）。
1.2 给一个数n，确定它的二进制表示中的第x位是0还是1？
1.3 位运算的优先级：
这个其实不需要特殊的记忆，只要知道，你要是想先运算哪一个，你就在哪一个加上括号就可以了。
硬要说位运算的优先级的话：
| 优先级 | 运算符 | 描述 | 结合性 |
|---|---|---|---|
| 1 | ~ |
按位取反（一元） | 从右到左 |
| 2 | <<, >> |
左移、右移 | 从左到右 |
| 3 | & |
按位与 | 从左到右 |
| 4 | ^ |
按位异或 | 从左到右 |
| 5 | | |
按位或 | 从左到右 |
但我感觉记这个不如直接用括号来的自在。
1.4 将一个数n的二进制表示的第x位修改成1
1.5 将一个数n的二进制表示的第x位修改成0
1.6 位图的思想：
1.7 提取一个数字n二进制表示中最右侧的1
-n的本质就是将最右侧的1的左边区域全部变成相反的。
1.8 干掉一个数n二进制表示中最右侧的1
n&(n-1) (n-1让最右侧的1的右侧部分（包含那个1）全部变成相反的）
1.9 异或(^)运算的运算律
1.a^0=a
2.a^a=0
3.a^b^c=a^(b^c)
32.力扣 面试题01.01判定字符是否唯一
32.1 题目解析：
题目真的很简单，这里就不过多的阐释了。咱们直接看算法思路：
32.2 算法思路：
咱们的第一种思路就是借助哈希表：
判断a是否在哈希表中，若不在，将他丢到哈希表中即可。以此类推，最后再来个遍历数组，看看是否还有剩余元素。
2.位图：
还记得咱们之前讲的位图嘛？没错，在这里用上了。并且这里需要用到前面的常规知识的2,3,4。
然后，咱们再来优化一下，就是由鸽巢原理，可得：若是len>26，那么一定有一个字符是重复的。所以若len>26，直接返回就可以了。
32.3 代码演示：
bool isUnique(string astr) {
if (astr.size() > 26) return false;//使用鸽巢原理来做优化
int bitMap = 0;//使用位图，之所以一开始定义为0，是因为一开始创建位图的时候，这里面是没有任何变量的。
for (auto x : astr)
{
int i = x - 'a';
if (((bitMap >> i) & 1) == 1) return false;//如果哈希表中已经有了这个数字，那么此时这个位置就等于1，就是false
//否则就加上这个数，将这里修改为1,此时才是表示有这个元素
bitMap = bitMap | (1 << i);//注意这里是i，不是x
}
return true;
}
int main()
{
string astr("leetcode");
cout << isUnique(astr) << endl;
return 0;
}32.4 总结反思：
注意，一开始进入位运算，一般都是以0开始的。所以让bitMap=0；
并且这里的运算，都是小范围的，就是bit为单位的运算。并且这里的for就相当于反复的循环了。
33 力扣. 268丢失的数字
33.1 题目解析：
题目很好理解，就是让你寻找本该在数组中，但是却没在的数字。
33.2 算法思路：
33.2.1 哈希表：
直接创建比数组元素多一个的哈希表。若有元素了，则加1，最后找到那个为0的即可。
33.2.2 高斯求和：
可以直接使用高斯求和：
就是ret=(0+5)(5+1)/2-数组中所有元素的和即可。
33.2.3 位运算（异或运算的运算律）
虽然思路是这么个思路，但其实代码所代表的意思还有点不同。
33.3 代码演示：
int missingNumber(vector<int>& nums)
{
int ret = 0;
for (auto x : nums)
{
ret ^= x;
}
for (int i = 0; i <= nums.size(); i++)
{
ret ^= i;
}
return ret;
}
int main()
{
vector<int> nums = { 3,0,1 };
cout << missingNumber(nums) << endl;
return 0;
}33.4 总结反思：
我已3，0，1为例子，大家就明白了：
ret^3^0^1^0^1^2^3,根据位运算的公式，是不是两个一样的可以消去。所以说，最后只剩下0^2，不就是2了嘛？
34 力扣. 371 两整数之和
34.1 题目解析：
题目非常之简单。
34.2 算法思路：
那么现在，就是如何存储这种移动呢？就是还是用int存储即可。
例如：int a=(x^y)....................
34.3 代码演示：
int getSum(int a, int b) {
while (b != 0)
{
int x = (a ^ b);
unsigned int y = (unsigned int)(a & b) << 1;//防止a&b出现-1，因为-1全是1，这样的话，左移1就没意义了
a = x;
b = y;//继续重复循环即可
}
return a;
}
int main()
{
int a = 4;
int b = 12;
cout << getSum(a, b) << endl;
return 0;
}34.4 总结反思：
本题没有什么特别的，只需要对位运算熟悉即可。
35. 力扣.137 只出现一次的数字II
35.1 题目解析：
题目也很好理解，那么咱们接下来就是直接讲解算法思路：
35.2 算法思路：
最后还得看a。若取模后为0，说明正好a的那一个比特位也为0.反之则为1.
往后拓展一下，若是n个相同的，那么后面就是模上n
35.3 代码演示：
int singleNumber(vector<int>& nums) {
int ret = 0;//记录结果的时候使用
for (int i = 0; i < 32; i++)//从这里开始，就是进入了比特位的计算
{
int sum = 0;//对于某一个比特位出现的数字的和
for (auto& x : nums)
{
if (((x >> i) & 1) == 1)//判断每一个元素的每一个比特位是否为1，若是1，sum++
{
sum++;//增加某一个比特位的数字和
}
}
sum %= 3;
if (sum == 1)//如果说余数为1，那么说明只有一个的那个数字的这个位置也为1
{
ret = ret | (1 << i);//之后让这个比特位变为1即可。若是0，则就不需要变
}
}
return ret;
}
int main()
{
vector<int> nums = { 2,2,3,2 };
cout << singleNumber(nums) << endl;
return 0;
}35.4 总结反思：
其实只要掌握好前面所说的一些计算方法，以及注意题目都是以小范围去做的，以bit单位去做的即可
36.力扣 面试17.19消失的两个数
36.1 题目解析：
大家看到这个困难题，有的就胆怯了。不用害怕，只要把题目理解透，基本不是问题。
36.2 算法思路：
其实这道题，很像两个题的综合：丢失的数字加上只出现一次数字III
不过呢，没做过也不要急。下面来分析一下：
1.将所有数全部异或在一起，由于nums出现了两次，（消完了），那么tmp=a+b
2.找到tmp中比特位上为1的那一位
a与b肯定不同，所以异或后肯定有一个位置为1，那么要么a为0，b为1.要么a为1，b为0
3.由于x位的不同，再次划分为两个异或
虽然有的时候，例如：a是一个int，但只要有>>或&等位操作符，基本就立马转移为那种32位的计算了。
36.3 代码演示：
vector<int> missingTwo(vector<int>& nums) {
//1.先将两个组合全部异或起来
int ret = 0;
for (auto& x : nums) ret ^= x;
for (int i = 1; i <= nums.size() + 2; i++) ret ^= i;//注意，这里的i的范围，完全是由题目的意思决定的，这里由于下面的数组比上面的多两个，所以要加2
//2.进行对这些的分类，找出比特位为1的那个
int diff = 0;//那个位置定义一个变量，用来表示不同
while (1)//由于两个数的不同，所以这里一定会跳出循环
{
if (((ret >> diff) & 1) == 1) break;//如果那个位置为1，那么直接跳出循环
else diff++;
}
//3.再次进行异或
int a = 0; int b = 0;
for (auto& x : nums)//需要注意的是，这里有两次异或
{
if (((x >> diff) & 1) == 1) b ^= x;//这里应该是x>>diff，因为判断的是x的diff比特位，下面的i也是一样的
else a ^= x;
}
for (int i = 1; i <= nums.size() + 2; i++)
{
if (((i >> diff) & 1) == 1) b ^= i;
else a ^= i;
}
return { a,b };//这里先让b异或，还是先让a异或，都可以的
}
int main()
{
vector<int> nums = { 2,3 };
vector<int> outcome = missingTwo(nums);
for (auto& e : outcome)
{
cout << e << "";
}
cout << endl;
return 0;
}
36.4 总结反思
可能你要是第一次做这种题，会感受到很别扭。我也是，但你做的多了，会发现，只要记熟练那几个公式，以及注意这个是小范围的运算。以及开始位运算，一般都是以0开始的（例如上面的ret=0）。即可
好了，本篇完.................