【优选算法 | 位运算】位运算基础：深入理解二进制操作
| 算法 | 相关知识点 | 可以通过点击 | 以下链接进行学习 | 一起加油！ |
|---|---|---|---|---|
| 双指针 | 滑动窗口 | 二分查找 | 前缀和 |
在本篇文章中，我们将全面解析位运算的基本原理与实际应用。位运算通过直接操作数字的二进制表示，能够在许多计算中提供极大的效率提升。无论是用于加速数学运算、优化算法，还是解决特定的技术问题，位运算都扮演着至关重要的角色。
🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏： 初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql
🌈你可知:无人扶我青云志 我自踏雪至山巅
文章目录
一、常见位运算总结
在二进制表示中，最右边的位是最低位，我们从这里开始计数。因此，下标的顺序与移位操作的顺序是对应的，这是一个约定。至于运算符优先级，通常不需要过于关注，只要能加括号，就尽量加上。
通过以下总结，在解决相关位运算问题会有很大的帮助。
关于6.7点证明
- -n的含义：按位取反再+1
- 第六点：本质是先全部取反，将最右侧的1为分界线，左边的区域全部变成相反
- 第七点：“n - 1：以最右侧的1为分界线，右侧区域的所有位都取反。如果需要借位，则从右侧开始依次借，直到借到最右侧的1。
二、入门题目
【题目】： 191. 位1的个数
【题目】：338. 比特位计数
【题目】：461. 汉明距离
面试题 01.01. 判定字符是否唯一
【题目】：面试题 01.01. 判定字符是否唯一
【算法思路】
对于面试题，通常有多种解法，面试官可以根据需求逐步提出新的要求，例如是否能将时间复杂度降低到常量级，或者是否有更优的解决方案。题目中提到‘如果不使用额外的数据结构，将会加分’。
在判断字符是否唯一的问题上，常见的做法是使用哈希表统计字符出现的次数。但我们也可以采用‘位图’的思路，利用一个int类型的32位整数来表示所有小写字母。每一位对应一个字符，如果某个字符出现过，就将对应的位设置为1，否则为0。这样，我们就能使用一个整数来充当‘哈希表’。
【优化方案】
这里需要一点数学功底，利⽤ "鸽巢原理"来做的优化 。题目中全部为小写字母，则最长无重复字符串大小为26，如果大于26直接返回就行了。
【代码实现】
classSolution{public:boolisUnique(string astr){if(astr.size()>26)returnfalse;int bitMap =0;for(auto& ch : astr){int x= ch -'a';//判断是否有重复元素if((bitMap >> x)&1==1)returnfalse;//修改x位置为1 bitMap |=(1<< x);}returntrue;}};268.丢失的数字
【题目】：268. 丢失的数字
classSolution{public:intmissingNumber(vector<int>& nums){int ret =0;for(auto& x : nums) ret ^= x;for(int i =0; i <= nums.size(); i++) ret ^= i;return ret;}};371.两整数之和
【题目】：371. 两整数之和
简而言之，无进位加法（通过异或操作）和进位加法（通过按位与操作得到的进位）是结合起来完成加法的。
步骤是：
- 异或（^）：计算两个数的“无进位加法”。它就像是普通的加法，但忽略了进位部分。
- 按位与（&）：计算进位部分。只有当两个数的相同位上都是1时，才会有进位。
- 左移进位：将进位移到下一位，准备继续与原数相加。
- 循环：每次重新计算无进位加法和新的进位，直到没有进位为止（进位变为0）。
这样，直到进位消失，最终结果就能得到正确的加法和。
【细节问题】：
- 关于不能使用加法和减法，通常使用位运算（如异或运算实现无进位加法）。
- 如果
(a & b)的结果是 -1，表示所有位都是 1。在位运算中，-1 通常表示无符号数下所有位都是 1，具体定义取决于无符号数的表示方式。
【代码实现】
classSolution{public:intgetSum(int a,int b){while(b !=0){int x = a ^ b;//无进制相加(进制不断添加)unsigned carry =(unsigned)((a & b)<<1);//获得进制 a = x; b = carry;}return a;}};137.只出现一次的数字 II
【题目】：137. 只出现一次的数字 II
设要找的数为 ret。由于数组中只有一个元素出现一次，其余元素都出现三次，我们可以通过对所有数的某一位进行按位求和，然后取模 3，来快速确定 ret 在该位上的值是 0 还是 1。通过这种方式，逐位恢复 ret 的每一位值，最终就可以还原出 ret。
对于"除某个元素仅出现 一次 外，其余每个元素都恰好 出现 N次"这类相关题目，都是可以使用"比特位计数"解决。(算法核心在图片中)
【代码实现】
classSolution{public:intsingleNumber(vector<int>& nums){int ret =0;for(int i =0; i <32; i++)// 依次去 修改 ret 中的每一位{int sum =0;for(auto x : nums)// 计算nums中所有的数的第 i 位的和if((x >> i)&1==1) sum++; sum %=3;if(sum ==1) ret |=(1<< i);}return ret;}};面试题 17.19. 消失的两个数字
【题目】：面试题 17.19. 消失的两个数字
【第一步】:将所有的数异或在一起
使用tmp变量将所有的数异或在一起，最终得到tmp = a ^ b。将问题转化为将a ^ b分隔开来。
【第二步】:找到tmp中，比特位为1的那一位
由于a和b是属于不同变量，必然存在一位比特位不相等，使用diff变量标记不同比特位的位置。
【第三步】:根据x位的不同，划分成两类异或
第二步和第三步是紧密联系的，第二步找到diff偏移量或者比特位不同的位置。那么可以将nums和全体数据按照"该比特位数据区分"，然后nums和全体数据使用异或，只剩下a或者b，a和b也被区分了。
本质就是如何去区分a和b，使用一个不同比特位,然后得到a + 一堆数据(不包含b)和b + 一堆数据(不包含a),全部按照统一指标，nums和全部数据区分不是重点，而是a和b也被区分开了，num和全部数据也可以被消除的
classSolution{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.找到相关位置int diff =0;while(1)if(((tmp >> diff)&1)==1)break;else diff++;//3.划分相关区域int a =0, b =0;for(auto 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};}};
快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！
