位运算基础

1.基础位运算

2. 给一个数n,确定他的二进制位中的第x为是0还是1

利用&(对应二进制位有0就是0)运算即可,将 n >> x后,他的第x为就在最右边,那么此时& 一个1,那么就只会得到1 或 0,如果是1,那么这个位上是1,反之则是0。

即 (n>> x) &1

3.将一个数n的二进制表示的第x位修改为1

方法: n | (1 << x) 即可:

4.将一个数n的二进制表示的第x位修改为0

方法: n & (~(1 << x)) 即可:

5.位图的思想

哈希表实际上大多数情况下是个数组,通过数组的内容来存储数据

实际上二进制位同样有这个效果:

通过二进制位上是0还是1来存储信息,而我们上面的1.2 ~ 1.4的方法主要是为了以后操作位图做好准备

6. 提取一个数n二进制表示中最右侧的1

方法: n & -n

-n操作实际上就是将原数取反后 +1 的操作

这样我们会发现,n与-n相比,原数最右侧的1的左边变成原来相反,右侧则不变,还是0

那么我们将 n & -n后,就能提取出最右侧的1

7. 去掉一个数n二进制表示中最右侧的1

方法: n & (n-1)

实际上n-1的操作就是从右往左进行借位的操作,因为在遇到最右侧的1之前,其余位都是0,是不够-1的,那么就要借位,直到遇见1

那么n-1后就得到与原来的n相比:最右侧的1(包括这个1)的右侧都是原来的相反数,而左侧的不变， 将n & n-1后,就能将原数最右侧的1去掉。

8. 异或运算的运算律

(1)a ^ 0 = a

(2)a ^ a = 0

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

丢弃的数字

题目链接

两个相同的数进行异或操作得到的是0 , 如果我们将原数组 和 完全的区间结合起来形成一个新的数组,那问题不就转化为只出现一次的数字的问题了吗,因为在新数组中,除了确失的那个数以外,其余数都出现了两次.

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

两整数之和

题目链接

两个整数相加,实际上对应的二进制相加的结果就是两个整数相加的结果

(1)对应位置相加

先把要相加的两个数进行异或,得到的就是未进位的和

(2)进位操作

实际上进位操作无非就是两个1相加那就进1,那么我们的&运算不正好满足对应二进制位两个为1才为1吗,只不过&运算的结果是在原位置,但是无妨,我们将得到的结果 << 1位即可。

最后将(1)的得到的数 与 (2)得到的数 再次进行^操作,此时还可能会有进位,因此这个操作我们要循环进行,直到(2)操作得到的数字为0,说明相加结果没有进位了,那么循环结束

class Solution {
public:int getSum(int a, int b) {while(b){int tmp = (a&b) << 1;a = a^b;b = tmp;}return a;}
};

只出现一次的数字II

题目链接

假设题目给我们的是如图所示的数组,只有一个元素出现了1次,其他的都出现了3次.我们将数组元素十进制转化为二进制,就会发现,如果我们将所有元素的某一个二进制位加起来,得到的结果去%3,得到的就一定是[只出现一次]的那个数的对应比特位.比如:我们将所有元素的第0比特位相加,那么就会得到4,4 % 3 = 1,那么99的第0位比特位就是0 。

class Solution {
public:int singleNumber(vector<int>& nums) {int ret = 0;for(int i = 0; i<32; i++)//依次修改ret每一位{int sum = 0;for(auto x : nums) // 统计nums中所有数第i位的和{if((x >> i) & 1 == 1)sum++;}sum %= 3;if(sum == 1)ret |= 1 << i;}return ret;}
};

消失的两个数字

题目链接

这里是引用我们完全的数字范围与 给定的数组合成一个新数组.假设我们的数组是:[2,3],那么数据范围就是1,2,3,4,那么新的数组就是:1,2,2,3,3,4 ;

然后将所有的数异或到一起 ， 就能得到消失的那两个数的异或结果；
异或不同为1，我们只要找到这个数为1的那一位，然后就可以利用这一位将 新的数组 分为两种，依次遍历，如果那位是 1 分一类， 不是1分一类，就可以分出来那两个数分别是多少。

class Solution {
public:vector<int> missingTwo(vector<int>& nums) {//1.先找出来缺的那两个数的异或结果int num = 0;for(auto x : nums)num ^= x;for(int i = 1; i<=nums.size()+2; i++)num ^= i;//2.找出a, b中比特位不同的那一位int diff = 0;while(1){if((num >> diff) & 1 == 1) break;else diff++;}//3.根据diff位的不同，将所有的数划分为两类int a = 0, b = 0;for(auto x : nums){if((x >> diff) & 1 == 1)a ^= x;else b^= x;}for(int i = 1; i<=nums.size()+2; i++){if((i >> diff) & 1 == 1)a ^= i;else b^= i;}return {a,b};}
};