【C/C++算法】从浅到深学习--- 位利用算法（图文兼备 + 源码详解）

绪论：打击蓝桥杯一起加油！！

逐日鼓励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry”
    绪论​：
本日总结了下位利用中常见的使用的方法，而且附加许多练习，通过方法 + 练习，位利用算法就将有很大的提升，后续将连续更新前缀和算法。敬请等待~
————————
早关注不迷路，话不多说安全带系好，发车啦（发起电脑观看）。
  

---

位运算

起首相识根本的位运算利用（必备）：

• <<：左移，全部位数左移（如：1111 << 1 = 1110）
  
• >>：右移，全部位数右移（如：1111 >> 1 = 0111）
  
• ~：取反，将全部位数全部取反（0 -> 1/ 1 -> 0）、如： ~1111 = 0000
  
• 至于 & 、| 、^ 看下图左边运算（001 与 011举行位运算利用，得到的效果）
  
• &：按位与，有0就是0
  
• |：按位或，有1就是1
  
• ^：按位异或，雷同为0，相异位1（大概可以当作无进位的加法）
  
  
  
  

• 约定下标从右往左的0开始：
  
  
  
  
• 如许某位置移动到0位置的移动值就是自己的下标
  
• 这里的下标，并不是数组中的真下标，而是我们在影象位数时它的位置的标识，从0开始到31（而且留意是从右往左的影象）
  
• 对于位运算的优先级，就不影象了，就经量使用括号
  

常用的根本位运算利用

• 判断一个数的二进制中第x位为0/1
  
  
  • 方法很简单 联合上面的>> 、 &位运算符
    
  • 此中留意在位运算中 会经常用到 1，来辅助位运算（由于他的二进制中只有1位：000… 0001，如许就能通过这一位举行利用，也能克制许多复杂题目）
    
  • 此处的话我们可以将 某个数举行右移>>x位，再 按位与x>> 上1（由于对与&来说，有0就是0，如许的话，按位与上1的话，若第x位上是0则为0，反之为1的话和按位与的1都没有0，就为1，而对于其他位来说差异管由于1的除了第一位为1其他都是0，按位与后都为0，以是效果只用两种大概 000…0000 / 000…0001）
    
  • 详细如下图假设
    
  • n为：…0110101001、
    
  • 1： …000…0001
    
  • 通过将n右移x位，将x位的值移动第一位，在与000…01举行按位与，即可得到答案
    
  
  

   对于背面的就不再细讲了，发起写草稿模仿环境就能很好的明白了，详细有题目可以品评。
  

• 将数 n 的二进制修改成1：n |= （1 << x）
  
  
  
  

   练习标题：leetcode 191 338 461
  

• 将一个数的二进制体现的第x位修改成 0：n &= (~(1<<x))
  
  
  
  
• 位图头脑：位图中我们就是通过 位利用举行管理此中的数据，位图内部告急通过0/1来判断该数据是否存在，我们可以用于存储一已知的容器数据但它访问速率大概较慢，那么可以将他在存放到位图中，如许通过 常量级的位利用就能快速的知道数据的状态。
  
  
  
  
• 提取一个二进制数中的最右侧的1：n &= -n
  
  
  
  
• 干掉二进制数中最右侧的1：n &= (n-1)
  
  
  
  
• 一些按位异或的运算律
  
  
  • a ^ 0 = a
    
  • a ^ a = a
    
  • a ^ b ^ c = a ^ (b ^ c)
    
  
  
• 对于a ^ b ^ c来说他的本质是：可以明白为按位异或利用是有互换律的，我们能同时的看三个数，它们的序次无所谓，那么也就能当作：抵消1的情势快速的算出答案（详细如下图）
  
  
  
  
  
  
  

   相干练习：LeetCode136、260
  怎样将 a ^ b 分别出来

此中就260比力特别和困难：这里讲一下

• 想通过 按位与利用得到两个单独的数据 a ^ b
  
• 如今须要将他给区分开
  
• 对于 a ^ b来说，若要区分可以通过找1，由于按位异或的本质是：雷同为0，相异为1
  
• 以是可以找到第一个差异的地方，也就是最右边的1
  
• 通过这个1的举行区分两个数，并将这两个数给分别通过按位异或的方式放到一个数组中
  
• 如许终极就能将这两个数放到两个数组中，也就能单独得到了
  

1. class Solution {
2. public:
3.     vector<int> singleNumber(vector<int>& nums) {
4.         int res = 0;
5.         for(auto c :nums){
6.             res ^= c;//利用到 res ^ res = 0 & res & 0 = res 这两个按位异或技巧
7.             //当res 在按位异或的过程中会将出现两次的给异或为0，而res 与 0 异或则还是res
8.         }
9.         //此时因为会有两个单独的值，所以res = a ^ b
10.         // 1001
11.         // 0011
12.         // 1010：a ^ b
13.         //此时找到 a ^ b 的最右边的1（这个代表他们不同的位）
14.         //通过这个区分 a b 这两个数，然后再次遍历nums中的元素
15.         //不过此时加上条件：通过 右移最右边这个数的下标i，后判断是否为1进行区分两数，将两数有分成了两种情况
16.         //这样 对于 右移最右边这个数的下标i 为1 / 不为1 中，肯定最终只会留下 a 和 b（因为其他的还是重复的然后抵消了）
17.         int i = 0;
18.         for(; i < 32;i++){
19.             if(((res >> i) & 1) == 1){
20.                 break;//代表找到最右边的1了
21.             }
22.         }
24.         int res1 = 0,res2 =0;
25.         //得到i的位置
26.         for(auto c : nums){
27.             if((c >> i) & 1 == 1){
28.                 //一份是：右移i位等于1的，同时也是 a ^ b中的某一位
29.                 res1 ^= c;
30.             }
31.             else{
32.                 res2 ^= c;
33.             }
34.         }
35.         vector<int> v{res1,res2};
36.         return v;
37.     }
38. };

复制代码

————
将上面8个常见的环境记取并练习，后在举行下面的练习进一步巩固
详细练习：

1. 判断字符是否唯一

标题：

分析标题并提出，办理方法：

• 本题不难想到，通过一个hash来快速简直定元素出现的个数
  
• 但标题给了一个小小的提升：能不能倒霉用额外的空间
  
• 那么本题仅仅26位，我们是不是可以通过位图的头脑：用一个整形来直接取代hash
  
  
  
  
• 联合前面的位利用，实现判断某个字符是否已经存在过
  
• 加上鸽巢原理：当字符串长度凌驾 26 时肯定会有重复的字符！！
  
• 修改x位为1：n|= (1 << i)
  

题解焦点逻辑：

1. class Solution {
2. public:
3.     bool isUnique(string astr) {
5.         if(astr.size() > 26 ) return false;//利用鸽巢原理进行优化
6.         //使用位图 代替hash
7.         int bit = 0;
9.         for(auto c : astr){
10.             int i = c - 'a';//得到字符的位置： 'a' - 'a' = 0、'b' - 'a' = 1
11.             //判断字符是否已经出现过：
12.             if((bit >> i & 1) == 1){
13.                 //进来代表第 i 位为1，并且代表已经出现过一次了
14.                 //所以就错误了，直接返回
15.                 return false;
16.             }
17.             bit |= (1 << i);//将第i位设置为 1
18.         
19.         }
20.         return true;
21.     }
22. };

复制代码

2. 丢失的数字

标题：

分析标题并提出，办理方法：

方法1：hash（空间复杂度：O（N））

• 先遍历添补hash
  
• 在遍历hash看哪个位置空了
  
  
  
  

高斯求和法：（（首项 + 尾项） * 项数）/ 2 便是全部元素的和，再减去数组中的和，如许就能得到缺失的和（空间复杂度：O（1））

方法3（本题解法）：位运算 a ^ a = 0（空间复杂度：O（1））

题解焦点逻辑：

本题就告急写位运算的利用：

1. class Solution {
2. public:
3.     int missingNumber(vector<int>& nums) {
4.         int n = nums.size();
5.         int res = 0;
6.         for(int i = 0; i <= n;i++){
7.             res ^= i;//得出 从 0 ~ n 的所以情况 0 ^ 1 ^ .... ^ n
8.         }
9.         for(auto i : nums){
10.             res ^= i;// res ^ nums = 缺失的
11.         }
12.         return res;
13.     }
14. };

复制代码

3. 两整数之和

标题：

分析标题并提出，办理方法：

对于这种不能使用 + - 法的一样寻常就是位运算了

• 起首回顾之前的按位异或利用又称无进位相加
  

按位异或的无进位相加

• 那么就须要找到他的进位值：发现当 a & b 时就能体现他是否须要进位（下图右边）
  

a & b 检察否须要进位

• 但这只是找到了他是否要进位的地方，我们还须要将他左移 1 位 从而完成进位后的低位++
  
  
  
  
• 然后再一次举行加法利用（按位异或：无进位加法）将进位值加上得到终极值
  
• 但留意：此时还须要再一次判断是否尚有进位的地方：
  
  
  • 若为0则体现不存在进位了
    
  • 若不为0则代表仍旧有进位，那么就须要再次重复2、3、4、5步（下图黑框框）
    
    
    
    
  
  

题解焦点逻辑：

1. class Solution {
2. public:
3.     int getSum(int a, int b) {
4.         //使用 ^ 的无进位相加
5.         //再使用 & 判断是否要进位（为0则代表不进位、不为0则代表有进位）
6.         while((a & b) << 1){
7.             int tmp = a;
8.             a = a ^ b;
9.             b = (tmp & b) << 1;
10.         }
11.         return a ^ b;
12.     }
13. };

复制代码

4. 只出现一次的数字 II

标题：

分析标题并提出，办理方法：

题解焦点逻辑：

1. class Solution {
2. public:
3.     int singleNumber(vector<int>& nums) {
4.         //将 nums 中的每个数的每一位 都相加并最终 模3，最终得到的每一位就是 只出现一次的每一位：为0 就是0，为1就是1
5.         //此处 还能 %n 这样就能 看出就能排除重复出现n次 得到只出现1次的
6.         int res = 0;
7.         // n * 32
8.         for(int i = 0 ; i < 32;i++){
9.             //使用一个sum计算，判断在该位置的和
10.             int sum = 0;
11.             //3n0 + 0 = 0 -%3-> 0
12.             //3n0 + 1 = 1 -%3-> 1
13.             //3n1 + 0 = 3n -%3-> 0  
14.             //3n1 + 1 = 3n + 1 -%3-> 1  
15.             for(auto c : nums){
16.                 //判断c位置上 i 下标下的值
17.                 if(((c >> i) & 1) == 1){//判断是否为1，为1则++
18.                     sum++;
19.                 }
20.             }
21.             sum %= 3;//判断只出现一次的那个数的下标
22.             if(sum == 1){
23.                 res |= (1 << i);//给结果下标添加算出来的值
24.             }
25.         }
26.         return res;
27.     }
28. };

复制代码

5. 消散的两个数字

标题：

分析标题并提出，办理方法：

分析标题不难通过前面的铺垫想出：

• 通过创建下同巨细的数组与缺失数组举行 按位异或 利用，终极会得到缺失两个数的 a ^ b
  
• 此时通过 a ^ b 找到它末了一位1的位置
  
• 将原数组和缺失数组都分成两份，而且这两份中会各自有a和b（获取没a和b）
  
• 如许再将分开的数组 相互 按位异或 就得到了分别缺失的两个a和吧
  

题解焦点逻辑：

1. class Solution {
2. public:
3.     vector<int> missingTwo(vector<int>& nums) {
4.         int n = nums.size() + 2;
5.         // 创建原数组,这里本质不用创建，直接不断 ^ 存储即可！
6.         int sum = 0;
7.         for(int i = 1 ; i <= n ;i++){
8.             sum ^= i;
9.         }
11.         //先与缺数数组相 按位异或
12.         int absent_value = sum;
13.         for(auto c : nums) {
14.             absent_value ^= c;
15.         }
17.         //得到了 a ^ b 缺失的值，现在找到第一个不同的位置
18.         int i = 0;
19.         for(; i < 32 ;i++){
20.             if((absent_value >> i) & 1  == 1){
21.                 break;
22.             }
23.         }
25.         //找到了i的位置，将原数组和缺失数组再次分成两份，再分别相异或
26.         vector<int> arr(2,0);
27.         for(int j = 1;j <= n;j++){
28.             if(((j >> i) & 1) == 1){
29.                 arr[0] ^= j;
30.             }else{
31.                 arr[1] ^= j;
32.             }
33.         }
35.         for(auto c : nums) {
36.             if(((c >> i) & 1)  == 1){
37.                 arr[0] ^= c;
38.             }else{
39.                 arr[1] ^= c;
40.             }
41.         }
43.         return arr;
44.         
45.         return arr;
46.     }
47. };

复制代码