当前位置：首页 > news >正文

【优选算法 | 位运算】位运算基础：深入理解二进制操作

news 来源：原创 2025/5/8 19:59:36

在这里插入图片描述

算法	相关知识点	可以通过点击	以下链接进行学习	一起加油！
双指针	滑动窗口	二分查找	前缀和

在本篇文章中，我们将全面解析位运算的基本原理与实际应用。位运算通过直接操作数字的二进制表示，能够在许多计算中提供极大的效率提升。无论是用于加速数学运算、优化算法，还是解决特定的技术问题，位运算都扮演着至关重要的角色。

请添加图片描述

Alt

🌈个人主页：是店小二呀
🌈C/C++专栏：C语言\ C++
🌈初/高阶数据结构专栏：初阶数据结构\ 高阶数据结构
🌈Linux专栏： Linux
🌈算法专栏：算法
🌈Mysql专栏:Mysql

🌈你可知:无人扶我青云志我自踏雪至山巅请添加图片描述

文章目录

一、常见位运算总结
二、入门题目
- 面试题 01.01. 判定字符是否唯一
- 268.丢失的数字
- 371.两整数之和
- 137.只出现一次的数字 II
- 面试题 17.19. 消失的两个数字

一、常见位运算总结

在二进制表示中，最右边的位是最低位，我们从这里开始计数。因此，下标的顺序与移位操作的顺序是对应的，这是一个约定。至于运算符优先级，通常不需要过于关注，只要能加括号，就尽量加上。

通过以下总结，在解决相关位运算问题会有很大的帮助。

在这里插入图片描述

关于6.7点证明

-n的含义：按位取反再+1
第六点：本质是先全部取反，将最右侧的1为分界线，左边的区域全部变成相反
第七点：“n - 1：以最右侧的1为分界线，右侧区域的所有位都取反。如果需要借位，则从右侧开始依次借，直到借到最右侧的1。

二、入门题目

【题目】： 191. 位1的个数

在这里插入图片描述

【题目】：338. 比特位计数

在这里插入图片描述

【题目】：461. 汉明距离

在这里插入图片描述

面试题 01.01. 判定字符是否唯一

【题目】：面试题 01.01. 判定字符是否唯一

在这里插入图片描述

【算法思路】

对于面试题，通常有多种解法，面试官可以根据需求逐步提出新的要求，例如是否能将时间复杂度降低到常量级，或者是否有更优的解决方案。题目中提到‘如果不使用额外的数据结构，将会加分’。

在判断字符是否唯一的问题上，常见的做法是使用哈希表统计字符出现的次数。但我们也可以采用‘位图’的思路，利用一个int类型的32位整数来表示所有小写字母。每一位对应一个字符，如果某个字符出现过，就将对应的位设置为1，否则为0。这样，我们就能使用一个整数来充当‘哈希表’。

【优化方案】

这里需要一点数学功底，利⽤ "鸽巢原理"来做的优化。题目中全部为小写字母，则最长无重复字符串大小为26，如果大于26直接返回就行了。

【代码实现】

class Solution {
public:bool isUnique(string astr) {if(astr.size() > 26) return false;int bitMap = 0;for(auto& ch : astr){int x= ch - 'a';//判断是否有重复元素if((bitMap >> x) & 1 == 1) return false;//修改x位置为1bitMap |= (1 << x);}return true;}
};

268.丢失的数字

【题目】：268. 丢失的数字

在这里插入图片描述

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

371.两整数之和

【题目】：371. 两整数之和

在这里插入图片描述

简而言之，无进位加法（通过异或操作）和进位加法（通过按位与操作得到的进位）是结合起来完成加法的。

步骤是：

异或（^）：计算两个数的“无进位加法”。它就像是普通的加法，但忽略了进位部分。
按位与（&）：计算进位部分。只有当两个数的相同位上都是1时，才会有进位。
左移进位：将进位移到下一位，准备继续与原数相加。
循环：每次重新计算无进位加法和新的进位，直到没有进位为止（进位变为0）。

这样，直到进位消失，最终结果就能得到正确的加法和。

【细节问题】：

关于不能使用加法和减法，通常使用位运算（如异或运算实现无进位加法）。
如果 (a & b) 的结果是 -1，表示所有位都是 1。在位运算中，-1 通常表示无符号数下所有位都是 1，具体定义取决于无符号数的表示方式。

【代码实现】

class Solution {
public:int getSum(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次"这类相关题目，都是可以使用"比特位计数"解决。(算法核心在图片中)

【代码实现】

class Solution {
public:int singleNumber(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和全部数据也可以被消除的

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.找到相关位置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};}
};

在这里插入图片描述
快和小二一起踏上精彩的算法之旅！关注我，我们将一起破解算法奥秘，探索更多实用且有趣的知识，开启属于你的编程冒险！

文章目录

一、常见位运算总结

二、入门题目

面试题 01.01. 判定字符是否唯一

268.丢失的数字

371.两整数之和

137.只出现一次的数字 II

面试题 17.19. 消失的两个数字

相关文章：