专题四_位运算( ＞＞ , ＜＜ , , | , ^ )_算法详细总结

目录

位运算

常见位运算总结

1.基础位运算

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

3.运算符的优先级

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

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

6.位图的思想

7.提取一个数（n）二进制表示中最右侧的 1 （lowbit）

8.干掉一个数（n）二进制表示中最右侧的 1

9.异或(^) 运算的规律

1. 判断字符是否唯⼀（easy）

解析：

1.暴力

2.位运算

总结：

2. 丢失的数字（easy）

解析:

1.暴力

2.位运算

总结：

3. 两整数之和（medium）

解析：

1.暴力：

2.位运算

总结：

4. 只出现⼀次的数字 II（medium）

解析：

1.暴力：

2.位运算：

总结：

5. 消失的两个数字（hard）

解析：

1.暴力：

2.位运算

总结：

位运算

常见位运算总结

1.基础位运算

  << : 数 n 的二进制左移x位                         按位与  &：有 0 就 0  (看&有没有很圆，长得很像0）

  >> : 数 n 的二进制右移x位                         按位或  | ： 有 1 就 1  (看|  是不是长得很像1)

  ~  (按位取反，所有位0变1，1变0）          异或运算 ^ : 相同为0 ，相异为 1 / 无尽位相加 

eg：

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

3.运算符的优先级

能加括号就加括号u，绝对不会错

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

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

那么就跟上一个思路一样，只要第x位，遇0，变0，即可。（&按位与）其他位全都&上一个1即可。

6.位图的思想

位图的思想其实就是哈希表

7.提取一个数（n）二进制表示中最右侧的 1 （lowbit）

n & (-n)  本质就是，得到最右侧的1，那么要考虑其他位都是于n 的每一位相反，但就是要保证最右侧的1，不变，然后&即可。

那么 （-n）就是先~（按位取反）再+1，就会让按位取反的1全都进位，变成0，知道遇到取反后的第一个0，变成1，就又变回了原来的1，然后再&即可。

8.干掉一个数（n）二进制表示中最右侧的 1

n & (n-1)  ,条件就是 n -1 就能一直向前借位，知道第一个不是0的1变成0.

再& ，就只会改变左边到借位这些位，全部都遇0，变0，到达删掉最右侧的1的效果 

9.异或(^) 运算的规律

1.a ^ 0 = a

2.a ^ a = 0 (消消乐)

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

^异或，再其数二进制的每一位上，相同为0，相异为1

那么就直接上例题：

1. 判断字符是否唯⼀（easy）

题目就是判断是不是字符串的字符是不是又重复的，但是不能借助任何数据结构，那么就可以考虑利用位运算，把字符当作比特位一样放在32位的数组里，如果有重复的，那么就可以利用比特位的0或1来判断。

解析：

1.暴力

不用多说，就是创建一个数组，来判断是否有字符的个数大于等于2，就返回false

2.位运算

利用一个int型32比特位来计算是否存在重复的字符，可以将字符s[i]-'a' 来存入这个32位里

class Solution {
public:
    bool isUnique(string astr) {
        int n=astr.size();if(n>26) return false;
        int bitMap=0;
        for(auto e : astr)
        {
            int i=e-'a';
            //判断该字符是否存在过
            if((bitMap>>i)&1==1) return false;
            //如果不是，我就要把第i位改成1；
            bitMap |= (1<<i);
        }
        return true;
    }
};

总结：

用bitMap来创建一个相当于int型的数组，i来存储每一位字符该移动的位数，那么就将bitMap>>i移动i位后，在跟1进行按位与，如果第一位都是1，那么就会得到1，说明之前就重复存在过，返回false

只要没有返回false 说明都是第一次出现，那么就将他bitMap这一比特位进行改变为1 ，先将1<<左移i位后进行或等于。遇1就改变。

2. 丢失的数字（easy）

这题题目意思比较简单，就是数组范围是[0,n] 那么他们就缺少一个数字x，对于ret进行^异或计算，^异或有消消乐的能力，也有无进位相加，那么进行消消乐，最后有一个数没有被消掉，就可以直接返回。

解析:

1.暴力

不用多少，排序后对数组的每一个元素跟[0,n]进行比较，如果有有一个不相等，那么就返回这个i

2.位运算

利用^异或运算，将没有消掉的数字进行返回就ok

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

总结：

^异或运算, 具有消消乐和无进位相加，那么这题就利用了消消乐的性质，翻译过来其实就是找到只出现了一次的数字这个意思，将出现了两次的数字给消掉了

3. 两整数之和（medium）

不使用加减得到两数之和，那么就肯定考虑的是位运算，利用上一题提到的^,无进位相加，具有相加性质，那么就可以进行运算

解析：

1.暴力：

其实像这种都是简单的面试题，如果未来机式，管他3*7=21，都是直接return a+b;

2.位运算

利用^ 异或运算，进行无进位相加，那么相加的都是无进位的，然后将这个值赋值给a，在单独求进位，这个时候你会发现(a&b) 就全是进位，但是都是本该进位的值在原来的位，所以全都要进一位，就全都要进行<<1左移1位，在赋值给b，在重复进行(a^b)，直到b无进位为止

class Solution {
public:
    int getSum(int a, int b) {
        while(b)
        {
            int x=a^b;
            int jinwei=(a&b)<<1;
            a=x;
            b=jinwei;//知道进位为0
        }
        return a;
    }
};

总结：

本题利用^异或运算进行无进位相加，但是仍具有相加性质，只要在单独加上进位即可（只需要发现(a&b)全都是进位）

4. 只出现⼀次的数字 II（medium）

题目意思挺简单的，就是找数组中只出现了1次的数字，其他数字都出现了3次，那么就不能像上一题一样用^异或运算，消掉两个重复出现的数字，那么就会让数组全变成一个数字，那么就考虑其他位运算解决，本题有点难理解，还是要用心体会。

解析：

1.暴力：

用哈希表，每当把整个数组相同的数字都存到一起，最后返回只出现了一次的数字，有点麻烦了，时间复杂度高，空间复杂度也高

2.位运算：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret=0;
        int n=nums.size();
        for(int i=0;i<32;i++)
        {
            int sum=0;
            for(auto e : nums) if((e>>i)&1) sum++; //计算nums中所有数的第i位的和是多少
            if(sum%3) ret |= (1<<i);
        }
        return ret;
    }
};

总结：

首先就是再数组中找到只出现一次的数字，其他的数字都是出现三次，由于题目不让额外开辟新空间，那么就是说明只能利用位运算进行计算
那么就要思考从哪下手，比如记录一个整个数组的所有位，（每个数都含有32位，占4个字节），那么我们使用位运算，将整个数组的同一位进行相加，eg:第1位 有3n个1+0 -> 3n 或者  3n个0 + 0 -> 0  等4种情况，因为都是出现3次，那么就把记录这个位出现的次数%3 =0 或则1 ，这就证明ret 这个只出现一次的这个数字，这一位就是这个0 或者1，那么就改变ret这32位里面的这一位，知道遍历完整个数组的所有32位即可

5. 消失的两个数字（hard）

虽然这题是困难题，但是只要弄得前面的题目真很easy

解析：

1.暴力：

那就是用数组，任何一个个比较，但是违反了题意

2.位运算

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int tmp=0;
        for(auto e : nums) tmp^=e;
        for(int i=1;i<=nums.size()+2;i++) tmp^=i;

        //那么现在只剩下a，b，找出比特位不同的那一位
        int diff=0;
        while(1)
        {
            if((tmp>>diff)&1) break;
            else diff++;
        } 

        //根据diff位进行计算未出现的数字
        int a=0,b=0;
        for(int i=1;i<=nums.size()+2;i++)
        {
            if((i>>diff)&1) a^=i;
            else b^=i;
        }
        for(auto e : nums)
        {
            if((e>>diff)&1) a^=e;
            else b^=e;
        }
        return {a,b};
    }
};