【优选算法篇】位运算小课堂：从入门到精通的奇妙之旅（上篇）

须知

💬 欢迎讨论：如果你在学习过程中有任何问题或想法，欢迎在评论区留言，我们一起交流学习。你的支持是我继续创作的动力！ 👍 点赞、收藏与分享：觉得这篇文章对你有帮助吗？别忘了点赞、收藏并分享给更多的小伙伴哦！你们的支持是我不断进步的动力！ 🚀 分享给更多人：如果你觉得这篇文章对你有帮助，欢迎分享给更多对C++算法感兴趣的朋友，让我们一起进步！

1. C++ 位运算算法 详解

1.1 位运算的重要性

位运算（Bitwise Operation）是计算机底层操作的核心。它的重要性体现在以下几个方面：

1. 高效性：位运算直接操作二进制位，速度极快，是最高效的运算方式之一。
2. 底层控制：用于硬件控制、网络协议、图像处理等领域，帮助开发者操作底层数据。
3. 空间优化：在数据压缩、哈希算法等场景中，通过位操作极大节省存储空间。
4. 算法核心：许多高效算法依赖位运算实现，比如快速幂、判断奇偶、位图等。

1.2 位运算的定义

位运算是对整数在二进制位层面进行操作的运算，主要包括以下基本操作：

1. 按位与（&）
   • 规则：两个二进制位都为 1 时，结果为 1；否则为 0。
   • 应用：常用于掩码操作，保留某些位的信息。
     • 示例：1101 & 1011 = 1001
2. 按位或（|）
   • 规则：只要有一个二进制位为 1，结果为 1；否则为 0。
   • 应用：设置某些位为 1。
     • 示例：1101 | 1011 = 1111
3. 按位异或（^）
   • 规则：二进制位相同为 0，不同为 1。
   • 应用：交换值、检测位差。
     • 示例：1101 ^ 1011 = 0110
4. 按位取反（~）
   • 规则：将每个位取反，即 1 变 0，0 变 1。
   • 应用：构造补码。
     • 示例：~1101 = 0010（假设为4位操作）
5. 左移（<<）
   • 规则：将所有位向左移动指定位置，右边补 0。
   • 应用：高效计算乘以 2^n。
     • 示例：1101 << 2 = 110100
6. 右移（>>）
   • 规则：将所有位向右移动指定位置。
     • 算术右移：高位用符号位填充，保留符号。
     • 逻辑右移：高位用 0 填充。
   • 应用：高效计算除以 2^n。
     • 示例：1101 >> 2 = 0011

1.3 位运算的核心思想

1. 二进制数据的直接操作：将复杂的逻辑转换为简单的二进制运算。
2. 高效替代算术操作：使用移位、与或操作完成加减乘除或逻辑控制。
3. 灵活的位级处理：针对数据的某些特定位进行精确控制和修改。
4. 组合运用：通过多种位运算的结合，构造高效的算法。

1.4 经典应用

1. 快速判断奇偶数
   • 思路：通过按位与操作 n & 1 判断奇偶。
     • 示例：5 & 1 = 1（奇数），4 & 1 = 0（偶数）
2. 交换两个数（不使用额外变量） a = a ^ b b = a ^ b a = a ^ b
   • 示例：a = 5, b = 7 -> a = 7, b = 5
3. 清零最低位的 1
   • 公式：n & (n - 1)
   • 作用：用于统计 1 的个数。
     • 示例：12 (1100) -> n & (n - 1) = 8 (1000)
4. 判断二进制中是否为 2 的幂
   • 公式：n > 0 and (n & (n - 1)) == 0
     • 示例：8 (1000) 是 2 的幂；10 (1010) 不是。
5. 位图（Bitmap）算法
   • 应用于海量数据处理，用位表示某个值是否存在，大幅节省空间。
     • 示例：检测某个数字是否出现。
6. 位掩码（Bitmask）操作
   • 用于权限管理（如读写执行权限），每个位表示一个权限状态。
     • 示例：111 表示 rwx 权限，101 表示 rw-。
7. 图像处理中的像素操作
   • 按位与、或操作对图像的颜色、透明度等位级数据进行精细控制。
8. 加法的位运算实现
   • 利用异或操作模拟加法：a ^ b（不进位加法）和 a & b（进位）。
9. 哈希函数优化
   • 通过位运算快速计算哈希值或减少冲突。
10. 网络编程中的子网掩码

• 使用按位与确定 IP 地址和子网的关系。

位运算的基础简单但应用广泛，掌握它不仅能提升代码效率，还能帮助开发者深入理解计算机的工作原理。

2. 题目1：位1的个数

题目链接：191. 位1的个数 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

算法核心思想

1. 逐位检查：
   • 利用右移（>>）操作，将 n 的最低位逐步移出，然后与 1 按位与（&）操作来检查这一位是否为 1。
   • 如果结果是 1，说明当前位是 1，计数器 count 增加 1。
2. 循环 32 次：
   • 因为输入是一个 32 位整数（int），需要从最低位到最高位依次检查所有 32 位。
3. 返回计数器：
   • 每次遇到 1 时，计数器增加，最终返回这个计数值。

2.2 代码详解

class Solution 
{
public:
    int hammingWeight(int n) 
    {
        int count = 0; // 初始化计数器，统计 1 的个数
        for (int i = 0; i < 32; i++) // 遍历 32 位
        {
            if (((n >> i) & 1) == 1) // 右移 i 位后，与 1 按位与，判断最低位是否为 1
                count++; // 如果是 1，增加计数
        }
        return count; // 返回汉明重量
    }
};

2.2.1 示例分析

输入：n = 11

二进制表示：00000000000000000000000000001011 逐步过程如下：

• i = 0: (n >> 0) & 1 = 000...0011 & 1 = 1 -> count = 1
• i = 1: (n >> 1) & 1 = 000...001 & 1 = 1 -> count = 2
• i = 2: (n >> 2) & 1 = 000...000 & 1 = 0 -> count = 2
• i = 3: (n >> 3) & 1 = 000...000 & 1 = 1 -> count = 3 最终结果：count = 3

2.3 时间复杂度与空间复杂度

1. 时间复杂度：
   • 循环固定执行 32 次（因为是 32 位整数）。
   • 每次循环中执行常数操作：右移和按位与。
   • 总时间复杂度为 O(1)，与输入值大小无关。
2. 空间复杂度：
   • 只使用了一个额外变量 count，因此是 O(1)。

2.4 改进优化

虽然代码的时间复杂度已经是 O(1)，但在某些场景下可以进一步优化位操作的效率，例如使用 n & (n - 1) 清零最低位的 1。 优化后的代码：

class Solution 
{
public:
    int hammingWeight(int n) 
    {
        int count = 0;
        while (n != 0) // 当 n 不为 0 时，逐位清零最低位的 1
        {
            n &= (n - 1); // 清零最低位的 1
            count++;
        }
        return count;
    }
};

2.4.1 优化思路：

• 每次操作将当前数字的最低位 1 清零，使得循环次数仅等于 1 的个数。
• 时间复杂度：O(k)，其中 k 是 1 的个数，适用于输入值中 1 的个数远小于 32 的情况。

2.5 总结

• 原始方法适合简单直接的逐位统计，适合入门和通用情况。
• 优化方法更高效，尤其在实际应用中，适用于稀疏数据（1 的个数较少）的场景。

3. 题目2:比特位计数

题目链接：338. 比特位计数 - 力扣（LeetCode）

题目描述：

3.1 算法思路：

1. 辅助函数 hammingWeight 的功能：
   • 作用：输入一个整数 n，计算其二进制中 1 的个数。
   • 思路：通过循环，逐位检查 n 的每一位是否为 1，如果是，则计数器增加。
   • 实现细节：
     • 使用右移运算符 >> 将数字逐位右移。
     • 与 1 进行按位与（&）运算，检查最低位是否为 1。
     • 循环 32 次（针对 32 位整数）。
2. 主函数 countBits 的功能：
   • 作用：从 0 到 n，依次调用 hammingWeight 计算每个数字中 1 的个数，并将结果存入数组 arr。
   • 思路：
     • 遍历所有数字 i，范围是 [0, n]。
     • 对每个数字 i 调用 hammingWeight，获取其二进制中 1 的个数。
     • 使用 arr.push_back(count) 将结果依次存入数组。
3. 整体流程：
   • 初始化数组 arr 用于存储结果。
   • 循环从 0 到 n，计算每个数字的 1 个数。
   • 返回结果数组 arr。

3.2 示例代码：

// 定义一个辅助函数，用于计算一个整数的二进制中 '1' 的个数
int hammingWeight(int n) 
{
    int count = 0; // 初始化计数器，用于统计二进制中 '1' 的数量
    for (int i = 0; i < 32; i++) // 遍历整数的 32 位（假设输入是 32 位整数）
    {
        // 右移 i 位，并用按位与操作提取最低位，检查是否为 1
        if (((n >> i) & 1) == 1) 
            count++; // 如果当前位是 1，计数器加 1
    }
    return count; // 返回 '1' 的总个数
}

// 定义一个类，包含主函数，用于生成从 0 到 n 每个数字的二进制中 '1' 的个数
class Solution 
{
public:
    // 主函数，生成结果数组
    vector<int> countBits(int n) 
    {
        vector<int> arr; // 定义一个向量用于存储结果，每个元素代表对应数字的二进制中 '1' 的个数
        int count1 = 0; // 临时变量，用于存储每个数字的 '1' 个数

        // 遍历从 0 到 n 的每个数字
        for (int i = 0; i <= n; i++) 
        {
            count1 = hammingWeight(i); // 调用辅助函数，计算当前数字的 '1' 个数
            arr.push_back(count1); // 将结果添加到结果数组中
        }

        return arr; // 返回结果数组
    }
};

3.2.1 代码详解

辅助函数 hammingWeight

int hammingWeight(int n) 
{
    int count = 0;
    for (int i = 0; i < 32; i++) // 遍历整数的 32 位
    {
        if (((n >> i) & 1) == 1) // 检查当前位是否为 1
            count++; // 如果是，增加计数
    }
    return count; // 返回 1 的个数
}

主函数 countBits

class Solution 
{
public:
    vector<int> countBits(int n) 
    {
        vector<int> arr; // 用于存储每个数字的汉明重量
        int count1 = 0;
        for (int i = 0; i <= n; i++) // 遍历从 0 到 n 的每个数字
        {
            count1 = hammingWeight(i); // 计算当前数字的二进制中 1 的个数
            arr.push_back(count1); // 将结果加入数组
        }
        return arr; // 返回结果数组
    }
};

示例分析

示例输入：n = 5

目标：生成从 0 到 5 的二进制中 1 的个数，即：

• 0 -> 0000 → 1 的个数 = 0
• 1 -> 0001 → 1 的个数 = 1
• 2 -> 0010 → 1 的个数 = 1
• 3 -> 0011 → 1 的个数 = 2
• 4 -> 0100 → 1 的个数 = 1
• 5 -> 0101 → 1 的个数 = 2

输出：[0, 1, 1, 2, 1, 2]

逐步过程：

1. i = 0 → 调用 hammingWeight(0) → 结果 0 → arr = [0]
2. i = 1 → 调用 hammingWeight(1) → 结果 1 → arr = [0, 1]
3. i = 2 → 调用 hammingWeight(2) → 结果 1 → arr = [0, 1, 1]
4. i = 3 → 调用 hammingWeight(3) → 结果 2 → arr = [0, 1, 1, 2]
5. i = 4 → 调用 hammingWeight(4) → 结果 1 → arr = [0, 1, 1, 2, 1]
6. i = 5 → 调用 hammingWeight(5) → 结果 2 → arr = [0, 1, 1, 2, 1, 2]

最终返回 arr = [0, 1, 1, 2, 1, 2]。

3.3 时间复杂度与空间复杂度

时间复杂度：

1. 主函数：从 0 到 n 遍历了 n + 1 个数字。
2. 辅助函数：每次调用 hammingWeight 执行了 32 次操作（检查 32 位）。
3. 总体复杂度：O(n * 32)，即 O(32n)，等价于 O(n)。

空间复杂度：

• 存储结果数组 arr，大小为 n + 1。
• 总空间复杂度为 O(n)。

3.4 优化思路

当前实现中，每次计算每个数字的汉明重量时，完全独立地逐位检查。可以通过 动态规划 优化，利用前一个数字的结果推导当前数字的汉明重量。优化方法为：

1. 观察规律：
   • 如果 i 是偶数，则 countBits(i) = countBits(i / 2)（右移一位，相当于去掉最低位）。
   • 如果 i 是奇数，则 countBits(i) = countBits(i / 2) + 1（最低位为 1）。
2. 动态规划实现：

class Solution 
{
public:
    vector<int> countBits(int n) 
    {
        vector<int> dp(n + 1, 0); // 初始化结果数组，dp[i] 表示数字 i 的汉明重量
        for (int i = 1; i <= n; i++) 
        {
            dp[i] = dp[i >> 1] + (i & 1); // 动态转移方程
        }
        return dp;
    }
};

1. 优化复杂度：时间复杂度降为 O(n)，空间复杂度仍为 O(n)。

3.5 总结

• 初始实现通过逐位计算每个数字的汉明重量，简单直观，时间复杂度为 O(n * 32)。
• 动态规划优化利用子问题结果，减少重复计算，时间复杂度降为 O(n)。

4. 题目3：汉明距离

题目链接：461. 汉明距离 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

算法分为两部分

1. 辅助函数 hammingWeight：
   • 计算一个整数的二进制表示中 1 的个数（即汉明重量，Hamming Weight）。
   • 通过逐位右移（>>）和按位与（&）操作，统计 1 的个数。
2. 主函数 hammingDistance：
   • 计算两个整数 x 和 y 的汉明距离。
   • 使用按位异或（^）操作找出 x 和 y 的二进制表示中不同的位，结果是一个新整数 s。
   • 调用 hammingWeight 函数统计 s 中的 1 的个数，即为汉明距离。

4.2 示例代码：

// 辅助函数：计算整数 n 的二进制表示中 '1' 的个数
int hammingWeight(int n) 
{
    int count = 0; // 初始化计数器，用于统计二进制中 '1' 的数量
    for (int i = 0; i < 32; i++) // 遍历 32 位（假设输入为 32 位整数）
    {
        // 右移 i 位，并与 1 进行按位与操作，检查最低位是否为 1
        if (((n >> i) & 1) == 1) 
            count++; // 如果最低位为 1，则计数器加 1
    }
    return count; // 返回二进制中 '1' 的总数
}

// 主类：用于计算两个整数的汉明距离
class Solution 
{
public:
    // 主函数：计算 x 和 y 的汉明距离
    int hammingDistance(int x, int y) 
    {
        // 按位异或操作，得到二进制中 x 和 y 不同的位
        // 异或规则：相同位结果为 0，不同位结果为 1
        int s = x ^ y;

        // 调用辅助函数 hammingWeight，统计异或结果中 '1' 的个数
        // 这些 '1' 的数量即为 x 和 y 的汉明距离
        return hammingWeight(s);
    }
};

4.2.1 代码逻辑详细解析

1. 辅助函数 hammingWeight：
   • 功能：统计整数 n 的二进制表示中 1 的个数。
   • 方法：通过逐位右移操作，依次提取最低位并判断是否为 1。
     • n >> i：将整数 n 右移 i 位。
     • (n >> i) & 1：提取右移后结果的最低位，并判断是否为 1。
   • 时间复杂度：固定遍历 32 位，时间复杂度为 O(32)，即 O(1)。
2. 主函数 hammingDistance：
   • 功能：计算两个整数 x 和 y 的汉明距离。
   • 方法：
     • 通过按位异或（x ^ y）操作，生成一个新的整数 s，其二进制表示中 1 的位置对应 x 和 y 不同的位。
       • 异或规则： 1 ^ 1 = 0 0 ^ 0 = 0 1 ^ 0 = 1 0 ^ 1 = 1
       • 因此，s 的二进制中所有的 1 表示 x 和 y 不同的位。
     • 调用 hammingWeight 函数，统计 s 中 1 的个数，作为 x 和 y 的汉明距离。
   • 时间复杂度：
     • 异或操作时间复杂度为 O(1)。
     • 调用 hammingWeight 时间复杂度为 O(32)，即 O(1)。

示例运行过程

示例输入

x = 1, y = 4

计算过程

1. x 的二进制表示：0001 y 的二进制表示：0100 按位异或：

x ^ y = 0001 ^ 0100 = 0101

• 异或结果为：0101。
• 调用 hammingWeight(5)：
  • 5 的二进制表示为：0101。
  • 遍历每一位：
    • 第 0 位：1 → count = 1
    • 第 1 位：0 → count = 1
    • 第 2 位：1 → count = 2
    • 第 3 位：0 → count = 2
  • 返回 count = 2。
• 最终返回汉明距离：2

输出

2

4.3 时间复杂度和空间复杂度

时间复杂度

1. 异或操作：按位异或操作的时间复杂度为 O(1)。
2. 辅助函数 hammingWeight：遍历 32 位，时间复杂度为 O(1)。
3. 总时间复杂度：O(1)。

空间复杂度

• 使用常量级的变量（如 count 和 s），不需要额外空间，O(1)。

4.4 代码特点

1. 优点：
   • 简单直观，通过辅助函数分离逻辑，代码结构清晰。
   • 时间复杂度和空间复杂度均为常量级，性能优良。
2. 可优化方向：
   • 优化 hammingWeight 函数，利用 n & (n - 1) 方法快速清除最低位的 1，减少迭代次数

优化后的辅助函数

int hammingWeight(int n) 
{
    int count = 0;
    while (n != 0) // 当 n 不为 0 时
    {
        n &= (n - 1); // 清除最低位的 1
        count++; // 每次清除后计数加 1
    }
    return count; // 返回二进制中 '1' 的总数
}

• 优势：循环次数等于 1 的个数，适用于二进制中 1 较少的情况，进一步提升性能。

完整优化代码

int hammingWeight(int n) 
{
    int count = 0;
    while (n != 0) 
    {
        n &= (n - 1);
        count++;
    }
    return count;
}

class Solution 
{
public:
    int hammingDistance(int x, int y) 
    {
        int s = x ^ y; // 按位异或，找出 x 和 y 不同的位
        return hammingWeight(s); // 统计不同位的数量（即 '1' 的个数）
    }
};

5. 题目4：只出现1的次数

题目链接：136. 只出现一次的数字 - 力扣（LeetCode）

题目描述：

5.1 算法思路

1. 异或运算的特性：
   • 异或（^）运算的规则：
     • a ^ a = 0（任何数与自己异或，结果为 0）
     • a ^ 0 = a（任何数与 0 异或，结果不变）
     • 异或满足交换律和结合律：a ^ b ^ c = a ^ c ^ b。
   • 因此，如果一个数出现两次，它们会相互抵消为 0。
   • 只出现一次的数与 0 异或后仍是其本身。
2. 核心逻辑：
   • 遍历数组中的每个元素，对每个元素执行 异或操作。
   • 最终，所有出现两次的数字会抵消为 0，只剩下那个出现一次的数字。

5.2 示例代码：

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0; // 初始化结果为 0
        for (auto s : nums) // 遍历数组中的每个元素
        {
            ret ^= s; // 异或操作：逐个元素与结果异或
        }
        return ret; // 返回出现一次的数字
    }
};

5.2.1 执行过程示例

输入示例

nums = [4, 1, 2, 1, 2]

执行过程

最终结果：4

5.3 时间复杂度与空间复杂度

1. 时间复杂度：
   • 遍历整个数组一次，每个元素进行一次异或操作。
   • 时间复杂度为 O(n)，其中 n 是数组的长度。
2. 空间复杂度：
   • 使用了一个整数 ret 进行累加异或，不需要额外的数据结构。
   • 空间复杂度为 O(1)。

5.4 多种解法

5.4.1 解法二：哈希表法

思路

1. 使用 哈希表 记录每个元素出现的次数。
2. 遍历哈希表，找到次数为1的元素。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> countMap;
        for (int num : nums) {
            countMap[num]++; // 记录每个元素出现的次数
        }
        for (auto& pair : countMap) {
            if (pair.second == 1) { // 找到只出现一次的元素
                return pair.first;
            }
        }
        return -1; // 兜底返回
    }
};

时间复杂度：O(n) — 遍历数组和哈希表

空间复杂度：O(n) — 额外使用哈希表存储元素及其频次

5.4.2 解法三：排序法

思路

1. 对数组进行排序，相同的元素会相邻。
2. 遍历排序后的数组，如果某个元素与前一个和后一个元素不同，它就是只出现一次的数。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序数组
        for (int i = 0; i < nums.size(); i += 2) { // 每次跳两个位置
            if (i == nums.size() - 1 || nums[i] != nums[i + 1]) { 
                return nums[i]; // 如果元素和下一个元素不同，返回该元素
            }
        }
        return -1; // 兜底返回
    }
};

时间复杂度：O(n log n) — 排序的时间复杂度

空间复杂度：O(1) — 如果排序算法为原地排序

5.4.3 解法四：数学法（2∗sum - sum）

思路

1. 利用集合（Set）去重后计算数组中元素的和。
2. 原始数组中所有元素之和减去去重后的和的两倍，结果就是只出现一次的数。

代码实现

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> numSet;
        int sumOfNums = 0, sumOfSet = 0;

        for (int num : nums) {
            sumOfNums += num; // 数组中所有元素的和
            if (numSet.find(num) == numSet.end()) { // 如果元素不在集合中
                numSet.insert(num);
                sumOfSet += num; // 记录集合中元素的和
            }
        }
        return 2 * sumOfSet - sumOfNums; // 根据公式计算结果
    }
};

时间复杂度：O(n) — 遍历数组

空间复杂度：O(n) — 额外使用集合

5.4.4 解法对比总结

5.5 总结

• 关键点：利用异或的特性，重复出现的数字会被抵消（a ^ a = 0），最终只剩下不重复的那个数。
• 优势：
  • 时间复杂度为 O(n)，一次遍历解决问题。
  • 空间复杂度为 O(1)，无需额外存储空间。
• 适用场景：数组中有且只有一个数字出现一次，其余数字均出现两次

6. 题目5：只出现一次的数字 |||

题目链接：260. 只出现一次的数字 III - 力扣（LeetCode）

题目描述：

6.1 算法思路：

思路解析

步骤1：使用异或找出两个数字的异或结果

1. 将数组中所有数字进行异或，最终结果 xorsum 是这两个不同数字的异或结果。
   • 原因：
     • 相同的数字异或为 0（a ^ a = 0）。
     • 0 与任何数异或不改变数值（a ^ 0 = a）。
     • 因此，数组中成对的数字会相互抵消，只剩下两个不同的数字的异或结果。
   • xorsum 的特点：
     • 它是两个只出现一次的数字的 异或值，即 xorsum = num1 ^ num2，其中 num1 和 num2 是结果。

步骤2：找到异或结果中最低的不同位（区分两组数字）

1. 异或结果 xorsum 中的 最低位的1，表示在这一位上，两个不同数字的二进制表示不同（一个是 1，另一个是 0）。
   • 通过 xorsum & (-xorsum) 找出最低的1位：
     • (-xorsum) 是 xorsum 的 补码，补码中保留最低位的1并将其他位取反。
     • xorsum & (-xorsum) 可以快速找到最低位的1。
2. 这位 lsb（lowest significant bit）可以将数组中的所有数字分为两组：
   • 第一组：在该位上为 1 的数字。
   • 第二组：在该位上为 0 的数字。

步骤3：分别异或两组数字，得到两个结果

1. 将数组中的所有数字根据最低位的1进行分组。
2. 对每一组的数字分别进行异或：
   • 在第一组中，所有成对的数字（出现两次的数字）会互相抵消，最终结果是 num1。
   • 在第二组中，所有成对的数字也会互相抵消，最终结果是 num2。

6.2 代码解析

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int xorsum = 0; // 用于存储所有数字的异或结果
        for (int num: nums) {
            xorsum ^= num; // 所有数字异或，最终结果是两个不同数字的异或值
        }

        // 找出 xorsum 中最低位的 1（用于区分两个数字）
        // 如果 xorsum 是 INT_MIN（最小负数），它本身只有最高位为 1，不会溢出
        int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));

        int type1 = 0, type2 = 0; // 用于存储两个只出现一次的数字
        for (int num: nums) {
            if (num & lsb) { // 根据最低位的1分组：该位为1
                type1 ^= num; // 第一组异或，得到 num1
            }
            else { // 该位为0
                type2 ^= num; // 第二组异或，得到 num2
            }
        }

        return {type1, type2}; // 返回结果
    }
};

6.2.1 示例执行过程

输入

nums = [1, 2, 1, 3, 2, 5]

步骤1：计算所有元素的异或结果

• 1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5 = 3 ^ 5 = 6（二进制 0110）
• 6 是 3 和 5 的异或结果。

步骤2：找到最低位的1

• xorsum = 6 → 二进制 0110
• xorsum & (-xorsum) = 2（最低位的1在第2位）。

步骤3：根据最低位的1分组

• 分组1（第2位为1的数字）：2, 2, 3
• 分组2（第2位为0的数字）：1, 1, 5

步骤4：分别异或两组

• 第一组：2 ^ 2 ^ 3 = 3
• 第二组：1 ^ 1 ^ 5 = 5

输出

[3, 5]（结果顺序不唯一）。

6.3 复杂度分析

时间复杂度分析

1. 第一次遍历：计算所有数字的异或，时间复杂度为 O(n)。
2. 第二次遍历：根据最低位的1分组并分别异或，时间复杂度为 O(n)。
3. 总体时间复杂度：O(n)。

空间复杂度分析

• 使用了常数额外空间，空间复杂度为 O(1)。

6.4 多种解法思路

6.4.1 解法二：哈希表法

思路

1. 使用哈希表记录每个元素的出现次数。
2. 遍历哈希表，找到出现次数为1的两个元素。

代码实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_map<int, int> freq; // 统计元素出现的频率
        for (int num : nums) {
            freq[num]++;
        }
        
        vector<int> result;
        for (auto& pair : freq) {
            if (pair.second == 1) { // 出现次数为1的元素
                result.push_back(pair.first);
            }
        }
        
        return result;
    }
};

复杂度分析

• 时间复杂度：O(n)，一次遍历数组和哈希表。
• 空间复杂度：O(n)，额外的哈希表空间。

6.4.2 解法三：排序法

思路

1. 对数组进行排序，相同的元素会相邻。
2. 遍历排序后的数组，如果某个元素与前后元素都不相同，则它是目标元素之一。

代码实现

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end()); // 排序数组
        vector<int> result;
        
        for (int i = 0; i < nums.size(); i++) {
            if ((i == 0 || nums[i] != nums[i - 1]) && 
                (i == nums.size() - 1 || nums[i] != nums[i + 1])) {
                result.push_back(nums[i]);
            }
        }
        
        return result;
    }
};

复杂度分析

• 时间复杂度：O(n log n)，排序的时间复杂度。
• 空间复杂度：O(1)，原地排序（如果排序算法是原地的）

6.4.3 解法对比总结

6.5 总结

1. 异或法是解决此类问题的核心思想，利用异或的性质实现高效解法。
2. 通过 最低位的1 将两个不同的数字区分开来，巧妙地将问题分解为两组。
3. 该解法时间复杂度为 O(n)，空间复杂度为 O(1)，性能最优。

7. 总结要点

1. 异或运算 是位运算解决重复出现问题的核心思想：
   • 相同为0，0与任何数异或等于数本身。
2. 位统计 + 取模：通过逐位统计 1 的个数，可以解决 K次出现问题。
3. 低位的1：通过提取最低位的1，可以将数字分组，解决两个目标数字的问题。

8. 最后

通过上面几个例题：「Single Number」的异或运算解法、「Single Number III」的异或+分组方法，以及**「Single Number II」的位统计与取模优化**，我们总结出位运算在数组问题中的高效应用。 位运算 通过将复杂的数字出现次数、分组、去重等问题转化为简单的位级操作（如异或、位统计、取模等），极大地提升了问题求解的效率。 在处理 元素重复出现问题、分组求解问题 以及 高效数值处理 等场景时，位运算展现出显著的性能优势，尤其适用于 大规模数据 和 时间复杂度敏感 的应用场景。

路虽远，行则将至；事虽难，做则必成

亲爱的读者们，下一篇文章再会！！！