在本篇当中我们将会复习之前在C语言阶段学习的各种位运算，并且在复习当中将再补充一些在算法题当中没有进行总结的位运算的使用方法，再总结完常见的位运算使用方法之和接下来还是和之前的算法篇章一样通过几道算法题来对这些位运算的方法技巧进行巩固。在解决算法题过程中还是通过题目解析、算法原理讲解、代码实现三步来解决。相信通过本篇的学习能让你对位运算有更深的理解，一起加油吧！！！
1.位运算复习与补充
在之前C语言的c语言常用操作符(2)我们就已经了解了移位操作符：<<、>>，按位与：&，按位或：|，按位异或：^，按位取反：~。
注：如果你完全忘记了这些操作符的使用建议先看之前的那篇进行复习之后再进行本篇的学习效果更好。
接下来我们就复习这些操作符的特点并且还会补充一些之前没有系统了解过的使用方法。
1.基础的位运算逻辑
<<和>>分别实现的是数据二进制位的左移和右移动
&进行两个操作数的运算时将两个数据的二进制位进行按位与运算，规则是相应位置两个二进制元素都为1时运算的结果才为1，否则就为0
|进行两个操作数的运算时将两个数据的二进制位进行按位或运算，规则是相应位置两个二进制元素都为0时运算的结果才为0，否则就为1
^进行两个两个操作数的运算时将两个数据的二进制位进行按位异或运算，规则是两个两个二进制元素不相同时运算的结果为1，相同就为0
以上的上个位运算的操作符简单总结就是：
&：有0就为0
|：有1就为1
^：相同为0，相异为1
2.给定一个数判定它的二进制表示是0还是1
如果要从给定的数当中判断其二进制的第x位是0还是1其实就需要使用按位与运算符，之后再将该数的二进制进行右移x位，最后再将结果和常量1进行按位与&，最后如果结果为1就说明原来给定地数地二进制位地第x位为1，否则就为0。
例如以下示例：
要判断数字185地二进制位当中地第四位是1还是0就使用以上描述地方式来求解
通过以上地求解就可以看出其第四位是1
那么以上表述地解决过程使用运算符表示就是：
(n>>x)&1 结果为1就表示对应地二进制位值为1，否则就为0
注：在此x为要查询的数字地二进制位置，n表示对应的数字
3.将一个数n的二进制表示第x位修改为1
在此要将给定的数字n的二进制表示的第x位修改为1就需要使用到按位或和左移操作符，具体过程就是先将数字1使用左移操作符将其的二进制位左移x位，之后再得到的结果和要进行判定的数进行按位或 | 运算这样就可以将原来的数字的二进制位第x位就被修改为1
在以上的实现过程当中就使用到了按位或运算符的实现原理，当两个操作数有1时计算的结果就为1.这就使得在原来给定的数二进制位当中的x位与1进行按位或运算时无论原来的是1还是0结果都会被修改为1
例如以下示例：
那么以上表述地解决过程使用运算符表示就是：
n|=(1<<x)
注：在此x为要修改的数字地二进制位置，n表示对应的数字
4.将一个数n的二进制表示第x位修改为0
在此要将给定的数字n的二进制表示的第x位修改为0就需要使用到按位与和左移操作符以及按位取反，具体过程就是先将数字1使用左移操作符将其的二进制位左移x位，之后再得到的结果和要进行按位取反，再将以上得到的结果和要进行判定的数进行按位与 & 运算这样就可以原来的数字的二进制位第x位就被修改为0
在以上的实现过程当中就使用到了按位与运算符的实现原理，当两个操作数有0时计算的结果就为0。在此我们使用按位与之前先使用了按位取反这就使得除了第x位以外二进制表示都变成1，x位变成了0，这就使得在原来给定的数二进制位当中的x位进行按位与运算时无论原来的是x位是1还是0结果都会被修改为0
例如以下示例：
那么以上表述地解决过程使用运算符表示就是：
n&=(~(1<<x))
注：在此x为要修改的数字地二进制位置，n表示对应的数字
4.位图的思想
位图其实就是在哈希表的基础之上进一步优化出来的，在之前我们一般都是创建整型的数组来模拟哈希表，但当使用哈希表每个下标只需要表示其元素存在或者不存在时也就是元素的情况只有0或者1的情况时，并且当要存储的数据量很大时使用整型来创建数组所需的内存空间也很大，因此在这种情况之下为了能进行更好的优化就引出的位图。
在此位图的基本思想就是将每一个二进制位来表示表示原先的数组下标的元素是否存在，如果存在此时对应的二进制位的值就为1，反之就为0。这样一个整型变量就可以表示，此时一个整型变量就可以来表示32个元素个元素是否存在。这样相比原来使用数组来模拟哈希表的情况就可以大大的节约空间。
5.提取一个数(n)二进制表示中最右侧的1
如果要提取出给定的一个数二进制表示当中最右侧的1就需要使用到以下的操作：
n&-n
以上进行的操作就是先将给定的n变为其的相反数之后再将得到的结果和原来的n进行按位与操作，这样最终得到的结果就可以将原来的二进制表示当中的最右侧的1提取出来。
那么以上的操作是具体是如何实现的，接下来就来看以下的示例
如果我们要将以上的n的二进制表示的最右侧的1提取出来，先将得到原来的相反数这个操作在二进制表示当中就是进行按位取反再加一
通过以上的图示就可以看出在进行按位取反和加1操作之后得到的结果和原先的n相比在二进制表示当中从最右侧的1左边的二进制相比原先的二进制都进行的取反，右侧的0保持不变 。
以上得到的结果再和原来的n进行按位与就能得到原来n最右侧的1。
6.去掉一个数(n)二进制表示中最右侧的1
如果要去掉出给定的一个数二进制表示当中最右侧的1就需要使用到以下的操作：
n&(n-1)
以上进行的操作就是先将给定的n减一之后再将得到的结果和原来的n进行按位与操作，这样最终得到的结果就可以将原来的二进制表示当中的最右侧的1去掉。
那么以上的操作是具体是如何实现的，接下来就来看以下的示例
如果我们要将以上的n的二进制表示的最右侧的1去掉，先将得到原来n-1与原来的n进行按位与操作
通过以上的图示就可以看出在进行n-1操作之后得到的结果和原先的n相比在二进制表示当中从最右侧的1右侧边（包含最右侧的1）的二进制相比原先的二进制都进行的取反，左侧的0保持不变 。
以上得到的结果再和原来的n进行按位与就能将原来n二进制表示最右侧的1去掉。
8. 位运算符的优先级
在此你可能对& | 等位运算的操作符的优先级已经遗忘了，但其实在使用位运算操作符当中只要记住能加括号就加括号这样就一定不会出现错误。
9.异或(^)运算的运算律
通过之前的学习就知道按位异或有以下的规律：
1.a^0=a
2.a^a=0
3.a^b^c=a^(b^c)
2. 位运算的算法题复习题
接下来我们将通过以下的几道算法题来巩固以上我们复习的位运算的知识
2.1 位1的个数
191. 位1的个数 - 力扣（LeetCode）
通过以上的题目描述就可以看出该算法题要我们实现的求出给定的正整数当中二进制表示当中1的个数。
那么要解决这道题就需要使用到以上提到的将给定数当中最右侧的1去除的的操作，在此只需要再创建一个变量count来统计进行去除操作的次数即可，最终当n为0时此时变量count的个数就是原给定的正整数二进制表示当中1的个数
实现代码：
class Solution {
public:int hammingWeight(int n) {//使用count变量来统计n内二进制1的个数int count=0;while(n>0){//将n内最右侧的1去除n=n&(n-1);count++;}return count;}
};
2.2 比特位计数
338. 比特位计数 - 力扣（LeetCode）
通过以上的题目描述就可以看出该算法题要我们实现的是从0到给定数n之间的全部数都的二进制标示中1的个数存储到对应的数组下标位置。
那么要解决这道题就需要从0到n对各个元素进行二进制表示中1的计算，此时还是使用n=n&(n-1)来进行1个数的计算。
代码实现：
class Solution {
public:vector<int> countBits(int n) {//返回的ret数组vector<int> ret(n+1);for(int i=0;i<=n;i++){//创建变量count来统计1的个数int count=0,tmp=i;while(tmp>0){tmp=tmp&(tmp-1);count++;}ret[i]=count;}return ret;}
};2.3 汉明距离
461. 汉明距离 - 力扣（LeetCode）
通过以上的题目描述就可以看出该算法题要我们实现的是求出给定的两个整数x和y二进制表示不同位的个数。
那么要解决这道题就可以使用按位异或再结合去除给定数二进制表示最右侧1。由于我们要求的是给定的x和y二进制表示当中不同位的个数，那么就可以先将ret=x^y，因为按位异或的运算逻辑，此时得到的ret当中二进制为1的为就表示该位置x和y的二进制表示是不同的。之后再使用ret=ret^(ret-1)得到ret二进制表示当中1的位数，使用count来统计个数，最终返回count即可。
代码实现：
class Solution {
public:int hammingDistance(int x, int y) {//创建count变量来统计ret内二进制表示1的个数int ret=x^y,count=0;while(ret>0){ret=ret&(ret-1);count++;}return count;}
};2.4 只出现一次的数字
136. 只出现一次的数字 - 力扣（LeetCode）
在这道算法题当中要我们实现的就是从给定数组当中找出只出现一次的数。
在此由于在数组当中其他的数都是出现两次，而只有一个数出现一次此时就可以使用按位异或操作来实现。具体的实现过程就是只需要将数组的元素全部使用按位异或，最终得到的结果就是只出现一次的数，在此就是使用到a^a=0；a^0=0
代码实现：
class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;for(auto x:nums){ret^=x;}return ret;}
};
2.5 只出现一次的数字 III
260. 只出现一次的数字 III - 力扣（LeetCode）
通过以上的题目描述就可以看出该算法题要我们实现的是在给定的数组当中找出两个只出现一次的数。
那么要解决这道撒算法题就需要使用到按位异或以及求给定数n二进制表示最右侧的1；首先由于给定的数组当中只有两个只出现一次的数，其他的数都是出现两次的，这就使得将数组全部数进行按位异或之后结果就为两个只出现一次的数按位异或的结果。右由于这两个数进行按位异或时最终二进制位当中为1的位一定是两个数在对应位置不同的结果。那么此时就可以依据该位置来将原来的数组划分为两部分，一部分就是在指定的二进制位为1；另一部分就是在指定的二进制位为0，这样两个只出现一次的数就会分别被划分到这两部分内。这样将两部分的元素分别进行按位异或就可以得到这两个数。
代码实现
class Solution {
public:vector<int> singleNumber(vector<int>& nums) {//防止溢出将t定义为有符号整型unsigned int t=0;//将数组nums的所有元素进行按位异或操作for(auto x:nums){t^=x;}int t1=0,t2=0;//得到t当中的二进制表示最右侧的1int c=t&(-t);//变量原数组进行分类for(auto x:nums){if((x&c)==0)t1^=x;else t2^=x;}return {t1,t2};}
};3.位运算算法练习题
在以上我们对之前了解过的算法题进行了复习，那么接下来就通过几道算法题来对学习的位运算知识进行巩固和提升，在此我们还是按照题目解析、算法原理讲解、代码实现三步来实现。
3.1 判断字符是否唯⼀
面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）
题目解析
在此根据题目描述就可以看出该算法题要我们实现的是对给定的字符串进行判断如果字符串当中没有出现重复的字符就将返回true，否则就返回false。
算法原理讲解
在此我们可以通过先创建一个map对象之后遍历给定的字符串每次将遍历到的字符存储到map对象内，遍历完之后在遍历map对象如果其内部出现一个键值对的值大于1就说明原字符串内字符不唯一。
以上的算法确实能解决这道算法题，但是在此我们使用到了map这个额外的数据结构，那么有什么不使用额外的数据结构的算法呢？
在此其实就需要使用到位图的思想了，由于题目给定的字符串只会包含小写的字符，那么在我们就只需要创建一个整型变量用其的二进制位表示就可以存储所有的情况。之后就只需要遍历原数组，每次遍历到字符元素再将其减去'a'之后再位图当中寻找此时的二进制位值是否为1，是的话就说明原字符串当中出现了相同的字符，如果遍历到字符串的结束还没有出现相同的字符就说明原字符串当中所有字符都是唯一的。
在此其实还要一个点可以优化就是根据“鸽巢原理”；当字符串的长度大于26时，此时的字符串内一定会出现重复的字符
代码实现
class Solution {
public:bool isUnique(string astr) {//判断原字符串长度是否大于26，是的话直接返回falseif(astr.size()>26)return false;int t=0;//遍历字符串astrfor(auto x:astr){int cur=int(x-'a');//当对应二进制位值变为0就直接返回flaseif((t>>cur)&1)return false;//若二进制位值为0就将该位置值修改为1else t|=(1<<cur);}return true;}
};3.2 丢失的数字
268. 丢失的数字 - 力扣（LeetCode）
题目解析
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组当中找出[0,n]未出现的那个数。
例如以上示例1当中n未3时那么要求数组当中数字的范围就是[0,3]，那么在通过查找就可以发现数组当中缺少的是数字2，那么返回的数字就是2
算法原理讲解
在该算法题当中要解决其实有很多的方式，但是在题目当中有以下的进阶提示
也就是说我们能否用O(n)的时间复杂度，O(1)的空间复杂度解决呢？
在此如果不创建额外的空间解决就不能使用哈希表了，那么其实就只剩下位运算和高斯求和可以解决问题了
在此位运算的方法是将0到n的数字全部按位异或起来，之后再将结果和数组当中元素全部按位异或起来最后得到的结果就是数组当中没有出现的那个数
高斯求和的方式就是先将0到n的等差数列求和的结果，之后遍历数组将之前得到的结果减去数组的全部元素值，最后得到的结果就是数组当中没有出现的那个数
代码实现
位运算法：
class Solution {
public:int missingNumber(vector<int>& nums) {int n=nums.size();int ret=0;for(int i=0;i<=n;i++){ret^=i;}for(auto x:nums){ret^=x;}return ret;}
};高斯求和法：
class Solution {
public:int missingNumber(vector<int>& nums) {int n=nums.size();int sum=(n*(n+1))/2;for(auto x:nums){sum-=x;}return sum;}
};3.3 两整数之和
371. 两整数之和 - 力扣（LeetCode）
题目解析
通过以上的题目解析就可以看出该算法题要我们实现的是不使用+和-，求出给定的两个数a和b的和
算法原理讲解
要不使用+和-解决就需要使用其他的运算来解决，在此其实就需要使用按位异或来解决，因为我们知道按位异或计算的本质就是无进位相加，那么再使用了按位异或之后只需要再将进位得到就可以算出最终的结果。
接下来就通过一个示例来分析算法的具体实现过程是什么样的
例如要计算13加14，先来看这两个数二进制位进行按位异或的结果是什么样的
接下来就需要计算进位，我们知道进位只有在两个数的二进制位都为1时才会出现，那么按位与就能满足要求，并且计算之后进位还要使用<<1 ,之后将得到的结果再和赋值给b之前a^b的结果赋值给a进行按位异或操作，之后一直重复直到进位计算出的结果为0时a和b按位异或的结果就是一开始a+b的结果
代码实现
class Solution {
public:int getSum(int a, int b) {while(b){int x=a^b;//防止负数出现越界问题将进位y定义为无符号整形unsigned int y=(unsigned int)((a&b)<<1);a=x,b=y;}return a;}
};3.4 只出现一次的数字 II
137. 只出现一次的数字 II - 力扣（LeetCode）
题目解析
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组当中找出只出现一次的数字，在此除该数字以外其他的数在数组当中都出现3次
算法原理讲解
在这道题当中由于数组当中其他的数是出现了基数次，那么就不能像之前其他元素出现两次那样将所有元素直接进行按位异或操作，而是要先设数位ret为0。
由于整个数组中，需要找的元素只出现了「一次」，其余的数都出现的「三次」，因此我们可以根
据所有数的「某⼀个比特位」的总和 %3 的结果，快速定位到 ret 的「⼀个比特位上」的值是
0 还是 1 。
这样，我们通过 ret 的每⼀个⽐特位上的值，就可以将 ret 给还原出来。
代码实现
class Solution {
public:int singleNumber(vector<int>& nums) {int ret=0;//将32个比特位依次计算for(int i=0;i<32;i++){int sum=0;for(auto x:nums){if((x>>i)&1==1)sum++;}int t=sum%3;if(t==1)ret|=(1<<i);}return ret;}
};3.5 消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
题目解析
通过以上的题目描述就可以看出该算法题要我们实现的是从给定的数组找出[1,n]当中两个缺失的数字。
算法原理讲解
这道题如果在是直接上手来写的就会比较困难，但是在之前我们已经解决了丢失的数字以及只出现一次的数字|||那么这道题其实也不是那么难了。
在此就只需要结合之前两道算法题的思想，先将将0到n的数以及给定数组当中的全部元素进行按位异或，那么得到的结果就是两个缺失的数字进行按位异或的结果。接下来就是0到n的数字以及给定的数组当中找出两个只出现一次的数字，这就和之前解决只出现一次的数字那道算法题一样了
代码实现
class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//创建变量s统计两个缺失的元素按位异或的结果unsigned int s=0;//变量n为数组加上缺少的元素之后的元素个数int n=nums.size()+2;for(int i=1;i<=n;i++){s^=i;}for(auto x:nums){s^=x;}int t=s&(-s);int ret1=0,ret2=0;//进行分类for(auto x:nums){if(x&t)ret1^=x;else ret2^=x;}for(int i=1;i<=n;i++){if(i&t)ret1^=i;else ret2^=i;}return {ret1,ret2};}
};以上就是本篇的全部内容了，接下来还会带来更多的优选算法，未完待续……
