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

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

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

🔥专栏：算法笔记

---

前言

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

一.位运算算法原理

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

二.判断字符是否唯一

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

后言

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