【优选算法篇】微位至简，数之恢宏——解构 C++ 位运算中的理与美
文章目录
C++ 位运算详解：基础题解与思维分析
💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。
👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！
🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习位运算的基础与进阶！
前言
在算法的世界里，位运算是一门精妙的技艺，简洁而高效，似微风拂水，看似无声，却能激起阵阵涟漪。位运算将每一位的状态变换化作算法中的魔法，使得复杂问题得以在比特的碰撞间被轻松解构。它是一种微观的语言，却能支撑起宏观的世界；它的每一次与或非移，仿佛是对数据世界的精确雕琢，将代码的力量发挥到极致。
本篇文章，意在带你走进位运算的世界，细数其中蕴含的算法之美。从最基础的字符判定到丢失数字的找回，从无进位加法的实现到位图的优化，每一道题目，都是对位运算逻辑的深层探索。我们会一步步揭开位运算的面纱，透过 C++ 语言的语法与语义，看见算法设计中隐藏的巧思与哲理。
愿这篇文章不仅能成为你算法学习中的指南，更能启发你在每一道“位”的转动中，感受代码的力量与数学的纯粹。让我们以最细微的单位为起点，探寻算法的浩瀚宇宙，在这片二进制的旷野中找到属于你的算法之道。
第一章：位运算基础应用
1.1 判断字符是否唯一（easy）
题目链接：面试题 01.01. 判定字符是否唯一
题目描述：
实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
示例 1：
- 输入：
s = "leetcode" - 输出：
false
示例 2：
- 输入：
s = "abc" - 输出：
true
提示：
0 <= len(s) <= 100s[i]仅包含小写字母- 如果不使用额外的数据结构，会很加分。
解法（位图的思想）
算法思路：
利用「位图」的思想，每一个「比特位」代表一个「字符」，一个 int 类型的变量的 32 位足够表示所有的小写字母。在位图中，如果一个比特位是 0，表示这个字符没有出现过；如果一个比特位是 1，表示该字符出现过。
因此，我们可以使用一个「整数」来充当「哈希表」：
-
字符映射：每个字符的出现与否可以映射到一个
bitMap中的比特位上。 -
位运算操作：
- 检测：检测字符是否已经出现过，使用
((bitMap >> i) & 1) == 1来检查第i位。 - 添加字符：使用
bitMap |= 1 << i将字符加入到bitMap中。
- 检测：检测字符是否已经出现过，使用
-
鸽巢原理优化：当字符串长度超过 26 时，必定有重复字符，可以直接返回
false。
C++ 代码实现
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;
}
};
易错点提示
-
位图的初始化与处理：
bitMap初始值为0，保证所有比特位均为0，即所有字符均未出现。
-
鸽巢原理优化：
- 如果
s的长度超过 26，必定有重复字符，可以直接返回false，减少不必要的遍历。
- 如果
-
按位判断与添加：
- 通过位移和按位或操作，确保每个字符的状态准确记录在位图中。
时间复杂度和空间复杂度
- 时间复杂度：
O(n)，其中n是字符串的长度，需要遍历字符串一次。 - 空间复杂度：
O(1)，仅使用一个int来存储位图。
1.2 丢失的数字（easy）
题目链接：268. 丢失的数字
题目描述：
给定⼀个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
- 输入：
nums = [3,0,1] - 输出：
2 - 解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 2：
- 输入：
nums = [0,1] - 输出：
2 - 解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
示例 3：
- 输入：
nums = [9,6,4,2,3,5,7,0,1] - 输出：
8 - 解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
示例 4：
- 输入：
nums = [0] - 输出：
1 - 解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
提示：
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- nums 中的所有数字都独⼊无二
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题？
解法（位运算）
算法思路：
设数组的大小为 n ，那么缺失之前的数就是 [0, n] ，数组中是在 [0, n] 中缺失一个数形成的序列。
如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数。
C++ 代码实现
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;
}
};
易错点提示
-
理解异或运算：
- 异或运算具有自反性和交换性，任何数与自己异或的结果为 0，任何数与 0 异或的结果为该数本身。
-
边界条件处理：
- 确保遍历过程中正确处理所有范围内的数字。
时间复杂度和空间复杂度
- 时间复杂度：
O(n)，其中n是数组的长度，需要遍历数组两次。 - 空间复杂度：
O(1)，仅使用一个整数变量来存储异或结果。
1.3 两整数之和（medium）
题目链接：371. 两整数之和
题目描述：
给你两个整数 a 和 b，不使用运算符 + 和 -，计算并返回两整数之和。
示例 1：
- 输入：
a = 1, b = 2 - 输出：
3
示例 2：
- 输入：
a = 2, b = 3 - 输出：
5
提示：
-1000 <= a, b <= 1000
解法（位运算）
算法思路：
- 异或
^运算本质是「无进位加法」，用于计算a和b在不考虑进位的情况下的和。 - 按位与
&操作用于计算a和b的进位部分，左移一位后表示将进位加到下一位。 - 不断更新
a为无进位和，b为进位值，重复以上步骤直到b变为0，表示没有进位了，a就是最终的加法结果。
C++ 代码实现
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;
}
};
易错点提示
-
理解位运算的含义：
- 异或运算
a ^ b可以有效地计算无进位相加的部分，而按位与a & b运算可以确定需要进位的部分。 - 将进位部分左移一位，表示加到更高一位上，这与常规加法的进位规则是一致的。
- 异或运算
-
为什么使用无符号整数类型：
- 题目限制的
a和b范围（-1000到1000）实际上不会超出int范围，因此在很多编译环境中即使使用int类型通常也可以通过测试。 - 但为了编写健壮的代码，尤其是处理可能的极值或边界情况时，推荐在位运算加法中使用
unsigned int来处理进位值。原因是：- 在 C++ 中，带符号整数（
int）在左移时，若超过其表示范围，可能导致未定义行为。而unsigned int在左移超过范围时，则会进行模 (2^{32}) 运算，这样可以保证结果在范围内“循环”。 - 这种处理方式可以确保即使位运算结果溢出，程序仍然能够稳定地获得正确的结果。
- 在 C++ 中，带符号整数（
- 题目限制的
-
确保循环终止条件：
- 注意循环条件
b != 0，确保在进位为 0 时停止。此时，a已经包含了最终的结果。
- 注意循环条件
时间复杂度和空间复杂度
- 时间复杂度：
O(1)，因为在 32 位系统上，位运算的次数是有限的，与输入值的大小无关。 - 空间复杂度：
O(1)，只使用了常数空间来存储中间变量。
为什么选择无符号类型来防止溢出
在 C++ 中，带符号整数在超出范围时的行为是未定义的；而无符号整数超出范围时会自动取模。选择 unsigned int 能够确保即使溢出，程序也会得到一个稳定的结果。例如，a = 0x40000000 和 b = 0x40000000（即 1073741824）在左移后超出 int 范围时，unsigned int 可以保证结果循环到范围内，而不会产生未定义行为。
这种方法不仅适用于该题目，也是一种编写健壮的位运算代码的好习惯。
1.4 只出现一次的数字 II（medium）
题目链接：137. 只出现一次的数字 II
题目描述：
给你一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了唯一一次的元素。
你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。
示例 1：
- 输入：
nums = [2,2,3,2] - 输出：
3
示例 2：
- 输入：
nums = [0,1,0,1,0,1,99] - 输出：
99
提示：
1 <= nums.length <= 3 * 10^4-2^31 <= nums[i] <= 2^31 - 1nums中，除某个元素仅出现一次外，其余每个元素都恰出现三次。
解法（比特位计数）
算法思路：
- 设要找的数为
ret。 - 由于整个数组中，需要找的元素只出现了一次，其余的数都出现三次，因此我们可以根据所有数的某一特定位的总和
% 3的结果，快速定位到ret的某个特定位上的值是0还是1。 - 通过
ret的每一个比特位上的值，就可以将ret还原出来。
C++ 代码实现
class Solution {
public:
int singleNumber(vector<int>& nums)
{
int ret = 0;
for(int i = 0; i < 32; i++) // 依次去修改 ret 中的每一位
{
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;
}
};
易错点提示
-
理解比特位计数的原理：
- 需要关注每一位的计数，并确保只针对出现一次的数的比特位进行处理。
-
循环的边界条件：
- 确保循环遍历每一位时，处理负数时的位运算没有产生意外结果。
时间复杂度和空间复杂度
- 时间复杂度：
O(n)，其中n是数组的长度，需要遍历数组多次，但每次遍历都只针对 32 位。 - 空间复杂度：
O(1)，仅使用常量空间来存储ret和sum。
1.5 消失的两个数字（hard）
题目链接：面试题 17.19. 消失的两个数字
题目描述：
给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
以任意顺序返回这两个数字均可。
示例 1：
- 输入：
[1] - 输出：
[2,3]
示例 2：
- 输入：
[2,3] - 输出：
[1,4]
提示：
nums.length <= 30000
解法（位运算 + lowbit）
算法思路：
该问题可以看作是 268. 丢失的数字 与 260. 只出现一次的数字 III 的组合问题。本题的核心在于利用异或操作与 lowbit 方法进行高效分组。通过以下步骤找到缺失的两个数字：
-
初始异或操作
将nums数组中所有数与[1, n + 2]区间内的所有数依次异或。由于异或的特点，相同的数字异或结果为0，最后会得到tmp，其值是两个缺失数字的异或结果a ^ b。此时tmp不为0，因为a和b是不同的数字，必然有某一位不同。 -
使用 lowbit 找到分组位
利用lowbit（获取tmp最低为1的位）找到tmp中的一个不为0的比特位diff。该位能区分两个缺失的数字，因为a和b在这一位上必然不同。
计算diff的方法为diff = tmp & -tmp，它提取tmp的最低有效位。 -
根据
diff进行分组异或
通过diff位对所有数字进行分组：将数组nums和[1, n+2]中的所有数根据diff位的不同分成两组，分别对每组进行异或：- 如果某数字在
diff位上为1，则将其与b异或； - 否则将其与
a异或。
由于其他成对出现的数字会在分组后各自抵消，最终
a和b的值就是这两个消失的数字。 - 如果某数字在
C++ 代码实现
class Solution {
public:
vector<int> missingTwo(vector<int>& nums)
{
// 1. 将所有的数异或在一起，得到 a ^ b
int tmp = 0;
for (int x : nums) tmp ^= x;
for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
// 2. 使用 lowbit 找到 a 和 b 中最低不同的位
int diff = tmp & -tmp; // 利用 lowbit 找到第一个不同的比特位
// 3. 根据 diff 位的不同，将所有的数划分为两类并异或
int a = 0, b = 0;
for (int x : nums)
if (x & diff) b ^= x;
else a ^= x;
for (int i = 1; i <= nums.size() + 2; i++)
if (i & diff) b ^= i;
else a ^= i;
return {a, b};
}
};
易错点提示
-
理解
lowbit的用途：
lowbit方法可以快速获取一个整数的最低为1的比特位，确保我们能高效地将两个缺失数字分开处理。这一步骤相当于找到了这两个数字的“区分特征”。 -
分组后的异或逻辑：
使用diff位对所有数字进行分组后，对每组进行异或操作。因为其他成对出现的数字在每组中互相抵消，最后保留的即为两个只出现一次的数字。 -
确保正确处理
diff位的计算和分组条件：
diff = tmp & -tmp提取了tmp的最低有效位（第一个不为0的位）。这一位能够保证a和b被正确分组，因此在进行分组异或时要格外注意diff的使用。
时间复杂度和空间复杂度
- 时间复杂度：
O(n)，其中n是数组的长度，需遍历所有数字一次。 - 空间复杂度：
O(1)，只使用常量空间来存储临时变量。
写在最后
位运算是算法世界中的点滴星辰，看似细微，却拥有改变全局的力量。在 C++ 中，位运算不仅仅是逻辑符号的堆叠，而是通过对每一个比特的操控，使得代码在有限的资源中发挥出无限的效能。从基础的字符判定到复杂的加法运算，位运算用简洁的方式诠释了算法的本质——那是一种近乎哲学的简约主义，以最小的构件描绘出最大的问题解决空间。
微观的位运算，如涓涓细流，涓滴不息，却汇成了庞大而稳定的算法结构。我们在加法中找到无进位的神奇，在查找中看到消消乐的奥秘，在位图中读出数据压缩的智慧。每一道位运算的题目，都是对代码效率的深思，每一个解法的背后，都是对数学美感的致敬。
数之深，位之微，若能在这片无声的数字原野中找到心中的算法之道，便是对这门艺术的最高赞礼。愿位运算的精妙，启发你在算法的道路上不断前行，不断探索，在这无垠的计算世界中找到属于你的高峰与星辰。
以上就是关于【优选算法篇】微位至简，数之恢宏——解构 C++ 位运算中的理与美的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️
原文地址：https://blog.csdn.net/2301_79849925/article/details/143489673
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！