C++算法
C++ 位运算详解：基础题解与思维分析
C++ 位运算详解涵盖五个经典算法题。包括判断字符是否唯一，利用位图思想优化空间；查找丢失数字，通过异或运算消去重复项；两整数之和，模拟无进位加法与进位逻辑；只出现一次的数字 II，统计比特位计数模三；消失的两个数字，结合异或结果与 lowbit 分组。所有解法均追求线性时间复杂度与常数空间复杂度，深入剖析位运算在算法设计中的高效应用与底层逻辑。
C++ 位运算详解涵盖五个经典算法题。包括判断字符是否唯一，利用位图思想优化空间；查找丢失数字，通过异或运算消去重复项；两整数之和，模拟无进位加法与进位逻辑；只出现一次的数字 II，统计比特位计数模三；消失的两个数字，结合异或结果与 lowbit 分组。所有解法均追求线性时间复杂度与常数空间复杂度，深入剖析位运算在算法设计中的高效应用与底层逻辑。
题目描述：
实现一个算法，确定一个字符串 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 中。false。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 来存储位图。题目描述：
给定一个包含 [0, n] 中 n 个数的数组 nums，找出 [0, n] 这个范围内没有出现在数组中的那个数。
示例 1：
nums = [3,0,1]2[0,3] 内。2 是丢失的数字。提示：
进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题？
算法思路：
设数组的大小为 n，那么缺失之前的数就是 [0, n]。如果我们把数组中的所有数，以及 [0, n] 中的所有数全部「异或」在一起，那么根据「异或」运算的「消消乐」规律，最终的异或结果应该就是缺失的数。
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;
}
};
O(n)，其中 n 是数组的长度，需要遍历数组两次。O(1)，仅使用一个整数变量来存储异或结果。题目描述：
给你两个整数 a 和 b，不使用运算符 + 和 -，计算并返回两整数之和。
示例 1：
a = 1, b = 23示例 2：
a = 2, b = 35提示：
-1000 <= a, b <= 1000算法思路：
^ 运算本质是「无进位加法」，用于计算 a 和 b 在不考虑进位的情况下的和。& 操作用于计算 a 和 b 的进位部分，左移一位后表示将进位加到下一位。a 为无进位和，b 为进位值，重复以上步骤直到 b 变为 0，表示没有进位了，a 就是最终的加法结果。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 运算可以确定需要进位的部分。int）在左移时，若超过其表示范围，可能导致未定义行为。而 unsigned int 在左移超过范围时，则会进行模 (2^{32}) 运算，这样可以保证结果在范围内'循环'。b != 0，确保在进位为 0 时停止。此时，a 已经包含了最终的结果。O(1)，因为在 32 位系统上，位运算的次数是有限的，与输入值的大小无关。O(1)，只使用了常数空间来存储中间变量。题目描述：
给你一个整数数组 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 还原出来。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 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？以任意顺序返回这两个数字均可。
示例 1：
[1][2,3]示例 2：
[2,3][1,4]提示：
nums.length <= 30000算法思路：
该问题可以看作是 丢失的数字 与 只出现一次的数字 III 的组合问题。本题的核心在于利用异或操作与 lowbit 方法进行高效分组。通过以下步骤找到缺失的两个数字：
nums 数组中所有数与 [1, n + 2] 区间内的所有数依次异或。由于异或的特点，相同的数字异或结果为 0，最后会得到 tmp，其值是两个缺失数字的异或结果 a ^ b。此时 tmp 不为 0，因为 a 和 b 是不同的数字，必然有某一位不同。lowbit（获取 tmp 最低为 1 的位）找到 tmp 中的一个不为 0 的比特位 diff。该位能区分两个缺失的数字，因为 a 和 b 在这一位上必然不同。
计算 diff 的方法为 diff = tmp & -tmp，它提取 tmp 的最低有效位。diff 进行分组异或：
通过 diff 位对所有数字进行分组：将数组 nums 和 [1, n+2] 中的所有数根据 diff 位的不同分成两组，分别对每组进行异或：由于其他成对出现的数字会在分组后各自抵消，最终 a 和 b 的值就是这两个消失的数字。
diff 位上为 1，则将其与 b 异或；a 异或。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)，只使用常量空间来存储临时变量。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online