位运算算法及习题 ，丢弃的数字 , 两整数之和 ,只出现一次的数字II

位运算基础

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};
    }
};