> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。
> 目标：熟练掌握位运算算法。
> 毒鸡汤：学习，学习，再学习 ! 学，然后知不足。
> 专栏选自：刷题训练营
> 望小伙伴们点赞👍收藏✨加关注哟💕💕
🌟前言分析
最早博主续写了牛客网130道题，这块的刷题是让同学们快速进入C语言，而我们学习c++已经有一段时间了，知识储备已经足够了但缺少了实战，面对这块短板博主续写刷题训练，针对性学习，把相似的题目归类，系统的刷题，而我们刷题的官网可以参考：
⭐知识讲解
这里我们不用文字讲述了，我们直接看看下面的图解，让我们了解什么是位运算算法：
🌙topic-->1
题目链接：1.位运算
题目分析：
实现一个算法，确定一个字符串 s 的所有字符是否全都不同，全部不同返回 true ，相同返回 false
算法原理：
- 解法一：（哈希表）
每个字母都映射在 hash[26] 中 ，再判断hash是否有重复的字母。
- 时间复杂度为：O(n)
- 空间复杂度：O(n)
- 解法二：
采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）
图解：
细节（优化）：
采用鸽巢原理（抽屉原理），来优化。
代码演示：
class Solution { public: bool isUnique(string astr) { // 使用鸽巢原理来做优化 if(astr.size() > 26) return false; int bitMap = 0; // 循环 for(auto ch : astr) { int i = ch - 'a'; // 先判断字符是否已经出现过 if( ( (bitMap >> i) & 1) == 1) return false; // 把当前字符加入到位图中 bitMap |= (1 << i); } return true; } };
🌙topic-->2
题目链接：2.位运算
题目分析：
给一个包含 [ 0 , n ] 中 n 个数的数组 nums，找出[ 0 , n ]缺失的数字，
- 如果[3,0,1]：缺失2
- 如果[0,1]：缺失1
算法原理：
- 解法一：（哈希表）
每个字母都映射在 hash[26] 中 ，再判断hash是否有重复的字母。
- 时间复杂度为：O(n)
- 空间复杂度：O(n)
- 解法二：（高斯求和）
这个公式就是高中的求和公式（等差公式求前 N 项）。
- 解法三：位图（我们讲解这个）
采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）
图解：
代码演示：
class Solution { public: int missingNumber(vector<int>& nums) // 消消乐 { int ret = 0; for(auto x : nums) ret ^= x; for(int i = 0;i <= nums.size();i++) ret ^= i; // 返回 return ret; } };
🌙topic-->3
题目链接：3.位运算
题目分析：
给两个数子字，求两个整数和（我们不能用 + -来计算）
这到题可以偷鸡直接返回 return a+b
算法原理：
- 解法：位运算
图解：
代码演示：
class Solution { public: int getSum(int a, int b) { while(b != 0) { int x = a ^ b; unsigned int carry = (unsigned int)(a & b) << 1;// 算出进位 a = x; b = carry; } return a; } };
🌙topic-->4
题目链接：4.位图运算
题目分析：
在一个数组中只有两类数字，一种是出现3次，另一种是出现1次，找出出现一次的数字。
算法原理：
- 解法：位图（我们讲解这个）
采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）
图解：
代码演示：
class Solution { public: int singleNumber(vector<int>& nums) { int ret = 0; // 依次去修改 ret 中的每一位 for (int i = 0; i < 32; i++) { int sum = 0; for (int x : nums) // 计算nums中所以的数的第 i 位的和 if (((x >> i) & 1) == 1) sum++; sum %= 3; // 判断 if (sum == 1) ret |= 1 << i; } return ret; } };
🌙topic-->5
题目链接：5.位运算
题目分析：
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
算法原理：
- 解法：位图（我们讲解这个）
采用位图的算法原理（这里不是直接创建一个位图，而是用位运算构建一个位图）
图解：
代码演示：
class Solution { public: vector<int> missingTwo(vector<int>& nums) { // 1. 将所有的数异或在⼀起 int tmp = 0; for (auto x : nums) tmp ^= x; for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i; // 2. 找出 a，b 中⽐特位不同的那⼀位 int diff = 0; while (1) { if (((tmp >> diff) & 1) == 1) break; else diff++; } // 3. 根据 diff 位的不同，将所有的数划分为两类来异或 int a = 0, b = 0; for (int x : nums) if (((x >> diff) & 1) == 1) b ^= x; else a ^= x; for (int i = 1; i <= nums.size() + 2; i++) if (((i >> diff) & 1) == 1) b ^= i; else a ^= i; return { a, b }; } };
🌟结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。
