【算法笔记】位运算算法原理深度剖析

【算法笔记】位运算算法原理深度剖析

🔥个人主页：大白的编程日记

🔥专栏：算法笔记

前言

哈喽，各位小伙伴大家好！上期我们讲了前缀和算法原理的深度剖析。今天我们来讲一下位运算算法原理！话不多说，咱们进入正题！向大厂冲锋！

一.位运算算法原理

• 常见位运算
  这些是我们必须要掌握的位运算。大家要数据熟记在心。
• 位图
  位图就是一种用二进制整形替换哈希表的思想 - 异或运算律
  异或支持交换律
  

二.判断字符是否唯一

2.1题目

• 题目：判断子否是否唯一
  

2.2思路分析

这里我们用到位图的思想替代哈希表

2.3代码实现

class Solution {
public:
    bool isUnique(string astr) 
    {
        if(astr.size()>26)//大于26就出现重复
        {
            return false;
        }
        int bitMap=0;//位图
        for(auto e:astr)
        {
            int i=e-'a';
            if((bitMap>>i)&1)//判断i位置的数是否重复
            {
                return false;
            }
            else
            {
                bitMap|=(1<<i);//记录出现
            }
        }
        return true;
    }
};

三.丢失的数字

3.1题目

• 题目： 丢失的数字
  

3.2思路分析

这里我们用异或的消消乐和交换律即可解题

3.3代码实现

class Solution {
public:
    int missingNumber(vector<int>& nums)
    {
        int n=nums.size();
        int tmp=0;
        for(int i=0;i<n;i++)//异或原数组
        {
            tmp^=nums[i];
        }
         for(int i=0;i<=n;i++)//异或0-n
        {
            tmp^=i;
        }
        return tmp;
    }
};

四.两整数之和

4.1题目

• 题目：两整数之和
  

4.2思路分析

这里我们可以采用异或的无进位。

4.3代码实现

class Solution {
public:
    int getSum(int a, int b) 
    {
        while(b)//当进位为0结束
        {
            int tmp=a^b;//无进位相加的结果
            int tmp1=(a&b)<<1;//算出进位的结果
            a=tmp;
            b=tmp1;
        }
        return a;
    }
};

五.只出现一次的数字2

5.1题目

• 题目：只出现一次的数字2
  

5.2思路分析

5.3代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret=0;
        for(int i=0;i<=31;i++)
        {
            int sum=0;
            for(auto x:nums)
            {
                if((x>>i)&1)//将所有数字的第i位数字的1相加
                {
                    sum++;
                }
            }
            if(sum%3)//根据sum%3确定当前数位是0还是1
            {
                ret|=(1<<i);
            }
        }
        return ret;
    }
};

六.消失的两个数字

6.1题目

• 题目：消失的两个数字
  

6.2思路分析

6.3代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums)
    {
        int a=0;//记录两个数异或结果
        for(int i=1;i<=nums.size()+2;i++)
        {
            a^=i;
        }
        for(auto x:nums)
        {
            a^=x;
        }
        int tmp=a&(-a);//记录第一个不同的比特位
        int b=0;
        for(int i=1;i<=nums.size()+2;i++)//分组异或
        {
            if(i&tmp)
            {
                b^=i;
            }
        }
        for(auto x:nums)
        {
            if(x&tmp)
            {
                b^=x;
            }
        }
        int c=a^b;
        return {b,c};
    }
};

后言

这就是位运算算法原理深度剖析。大家自己好好消化。今天就分享到这里，感谢各位的耐心垂阅！咱们下期见！拜拜~