文章目录
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++ 位运算中的理与美的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️