【算法笔记】位运算算法原理深度剖析
【算法笔记】位运算算法原理深度剖析
🔥个人主页：大白的编程日记
🔥专栏：算法笔记
文章目录
- 【算法笔记】位运算算法原理深度剖析
前言
哈喽，各位小伙伴大家好！上期我们讲了前缀和算法原理的深度剖析。今天我们来讲一下位运算算法原理！话不多说，咱们进入正题！向大厂冲锋！
一.位运算算法原理
- 常见位运算
这些是我们必须要掌握的位运算。大家要数据熟记在心。
- 位图
位图就是一种用二进制整形替换哈希表的思想
- 异或运算律
异或支持交换律
二.判断字符是否唯一
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}; }};
后言
这就是位运算算法原理深度剖析。大家自己好好消化。今天就分享到这里，感谢各位的耐心垂阅！咱们下期见！拜拜~
