位运算 算法的学习与习题

目录

1.基础位运算的知识

1.1给定一个数字n，确定二进制第x位是1还是0

1.2将一个二进制数的第x位变成1或者0

1.3位图

1.4提取一个数最右侧的1

1.5去掉最低位的1

1.6亦或的运算律

2.位运算习题

2.1判定字符是否唯一

2.2丢失的数字

2.3两整数之和

2.4只出现一次的数字II

2.5消失的两个数字

1.基础位运算的知识

<<左移，整体向左移动一位，右侧补0

>>右移，整体向右移动一位，左侧正数补0，负数补1

~按位取反

&按位与，有0则0

|按位或，有1则1

^亦或，可以理解为相同为0，不同为1，或者不进位相加

按照8位二进制的数字来简单讲解一下上面知识

例如现在有两个数字，10：0000 1010 /27：0001 1011

10左移一位，结果是0001 0100，10右移一位，结果是：0000 0101

将10按位取反，结果是1111 0101

10和27按位与，结果是0000 1010，10和27按位或，结果是0001 1011

10和27亦或，结果是0001 0001

这一块并不难，写几个数字练习一下就行

1.1给定一个数字n，确定二进制第x位是1还是0

例如一个二进制数，00101101，想确定第3位是1还是0，可以将n右移x位，然后和1进行按位与

注意这里我们从右侧开始计算位数，并且是从第0位开始计算，因为这样想知道第几位，向右移动几位即可，因为1除了最后一位都是0，将n右移x位相当于将第x位移动到最后一个位置，最终按位与的结果只和第x位相关，所以这样可以确定第x位是0还是1

1.2将一个二进制数的第x位变成1或者0

例如这个数，0011 0011，想将第二位修改成1，只需将1左移两位，让0000 0100和原数进行按位或即可，因为按位或有1则1，所以这样做只会对第x位进行修改

类似的方法，想将第一位修改成0也非常简单，只需将1移动一位，然后按位取反，最后的结果和原数进行按位与即可，这样可以保证其他位不变的同时，只让第x位和0进行一个按位或，修改成0

1.3位图

比如一个长度为5的数组，可以用每一位存储信息，但是我们也可以不用数组，只用一个数字的每一位的01变换，去存储信息

比如00000000 00000000 00000000 00000000，一个数字有32位（32位环境），每一位是1或者0可以存储对应的一种信息，这样可以节省空间

1.4提取一个数最右侧的1

先说结果，例如一个数字n，最终结果是n&(-n)，也就是n和-n按位与即可

例如一个正数n，他的最右侧的1在第x位，将n取反之后，根据补码的知识，负数补码是除了符号位之外，按位取反+1，那么就可以让n和-n只有第x位是相同的

举一个具体例子0100 1000（这里为了方便，采用八位有符号二进制）

先是负数原码：1100 1000，补码为1011 0111+0000 0001，也就是1011 1000

因为第x位是最低的1，所以第x位右侧本来全是0，进行按位取反之后，第x位变成0，右侧全部变成1，此时再加1，右侧全部进位，最终使得第x位还是1，并且右侧依旧全是0

至于第x位左侧全部取反之外，没有其他变化，所以我们发现，将n和-n进行按位与之后，第x位左侧和右侧都会变成0，只留下第x位的1，这样就取出了最低位的1，也就是0000 1000，注意这里提取1的含义是，二进制表示下只有一个1，并不是数值为1

1.5去掉最低位的1

因为最低位的1，在减一之后，右侧的0会全部变成1，而自己变成0，其他位保持不变，所以只需要n&(n-1)，即可去掉最低位的1

1.6亦或的运算律

a^a=0

0^a=a

a^b^c=a^(b^c)

注意亦或可以满足交换律，因为可以每一位的不进位相加，所以可以看作加法，满足交换律

2.位运算习题

2.1判定字符是否唯一

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

这道题很明显可以用哈希表的方式，每次有新元素就丢进哈希表，判断是否有重复即可

但是我们也可以用位图的思想，因为输入只有小写字母，最多就26种情况，而int可以有32位的比特位，所以利用位图即可快速实现和哈希表一样的功能，当某个字母对应的位置为0，说明还没有该字母，如果为1，说明已经有这个字母了

逻辑也非常简单，根据字母的ascii码表，每个字母和a之间的距离作为在位图的位置，遍历到某个字母，将该位置设为1即可

代码部分

每次遍历到新位置，就判断该字母对应的位置是否已经是1了，如果是0就将该位置设为1，如果是1说明重复了，那么返回false

class Solution { public: bool isUnique(string astr) { int ret=0; for(auto e:astr){ int len=e-'a'; if((ret>>len)&1)return false; else ret|=(1<<len); } return true; } };

2.2丢失的数字

268. 丢失的数字 - 力扣（LeetCode）

这是一个乱序的数组，所以不能用二分来解，但是我们学过亦或的计算，让0依次亦或给定数组，和给定数组补全后的数组，进行两次循环亦或，我们可以得出，两次循环亦或完剩下的结果，就是丢失的数字

也许有点抽象，我们举个例子，比如示例1，数组【3，0，1】，完整的数组应该是【0，1，2，3】，因为亦或满足交换律，所以对应完整的数组我们直接当作有序也没问题，已知a^a=0，也就是相同的数字亦或之后相当于消除了，0^a=a，也就是和0亦或不影响数字本身

所以1和1，3和3，0和0都已经亦或之后变成了0，最后就是0^2，结果是2，所以亦或的最终结果就是丢失的那个数字，因为它没有相同数字进行亦或，仍然存在

代码部分

class Solution { public: int missingNumber(vector<int>& nums) { int ret=0; for(int i=0;i<=nums.size();i++){ ret^=i; } for(auto e:nums){ ret^=e; } return ret; } };

2.3两整数之和

371. 两整数之和 - 力扣（LeetCode）

这道题就需要应用亦或等价于无进位相加的思想来解

因为亦或相当于无进位的一次相加，那么只需要将需要进位的那些位置找到，补足进位即可

注意到，只有两个数字均为1的时候，会丢失一个进位，所以使用一次按位与，即可找到原本需要向前进位的位置，然后将结果向左移一位，并和亦或完的结果再次亦或，相当于把进位补上，但是有可能又遇到11亦或的情况，所以要反复这个过程，直到没有需要进位的操作

代码部分

class Solution { public: int getSum(int a, int b) { //亦或相当于进行不进位相加 //按位与相当于找到进位的位置，然后左移一位，是需要+1的位置 //所以亦或完的结果和按位与移动结果再次亦或 //相当于把缺少的进位补上 //直到不需要进位 while(b){ int x=a^b; b=(a&b)<<1; a=x; } return a; } };

2.4只出现一次的数字II

137. 只出现一次的数字 II - 力扣（LeetCode）

对于除了目标元素以外的数字，均出现了三次，也就是说，对于二进制的第x位，如果目标数字是0，该位置上的数字的累加和一定是3的倍数，因为其他数字，如果该位置是1，一定会有三次1加上去，最极端也就是该位置不存在数字，0是3的0倍也是合理的

而如果目标数字在该位置是1，最终结果肯定是3n+1(n根据情况而定)，所以我们只需要依次统计每一个位置数字的累计和，然后%3就是最后的结果，如果目标数字在该位置是0，那么3n%3=0，如果位1，那么3n+1%3=1，就可以去除掉其他数据的干扰，最终得到只出现一次的数字

代码部分

class Solution { public: int singleNumber(vector<int>& nums) { int sum=0; int ret=0; for(int i=0;i<32;i++){ ret=0; for(auto e:nums){ ret+=(e>>i)&1; } ret%=3; sum|=(ret<<i); } return sum; } };

2.5消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

这道题同样可以使用亦或的方法进行解题，根据刚才第二题的经验，我们想到了将所有数字进行亦或，也就是亦或丢失数组和完整数组，最终会得到一个数字，但是这个数字是丢失的两个数字亦或的结果，注意这两个数字因为不可能重复，所以至少有一位不同，也就是亦或结果的二进制表示，至少存在一个1

这个1就表示，在该位置，这两个数字一个是0一个是1，那么我们就通过最低位的1来进行分类，将所有数据分为两类，一类是该位置为0的数字，一类是该位置为1的数字

那么我们可以走两路亦或，相当于是把两个数字拆开放到两个数组里，做两次丢失的数字即可

代码部分，lowbit就是最低位1的一个分类标准，根据该数字和lowbit按位与的结果，判断该位置是1还是0，进行分别的亦或，最终就可以得到两组亦或的结果，就是消失的两个数字

class Solution { public: vector<int> missingTwo(vector<int>& nums) { int ret=0; for(int i=1;i<=nums.size()+2;i++){ ret^=i; } for(auto e:nums){ ret^=e; } int lowbit=ret&(-ret); int a=0; int b=0; for(auto e:nums){ if(e&lowbit)a^=e; else b^=e; } for(int i=1;i<=nums.size()+2;i++){ if(i&lowbit)a^=i; else b^=i; } return {a,b}; } };