【优选算法篇】计算机背后的秘密武器：位运算的超能力（下篇）

须知

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

接上篇：【优选算法篇】探索位运算的宇宙：简单规则背后的复杂逻辑（中篇）-CSDN博客

引言：通过上篇文章带大家简单了解“位运算算法”，小试牛刀。接下来将让大家感受一下位运算在解题的妙处。

位运算在校招中的重要性主要体现在以下几个方面：

1. 提升算法效率：位运算常用于优化时间复杂度，尤其是在处理大量数据时，能大大提高算法的执行效率。面试中常通过位运算解决一些经典问题（如加法、乘法、查找重复元素等）。
2. 基础数据结构与算法题：许多经典的算法题（如哈希、最小公倍数、最大公约数、判断奇偶等）都能通过位运算高效解决，这也是面试中的常见考察点。
3. 简洁的解决方案：通过位运算可以用少量的代码实现复杂的逻辑，这种简洁高效的解决方案在面试中非常加分。
4. 思维锻炼：位运算需要对二进制和底层实现有较强的理解，能够提高面试者的逻辑思维和算法设计能力。

1. 回顾

通过上篇博客简单讲解了，接下来步入位运算的最终正轨之路。-> 博客介绍了位运算在实际编程中的应用，特别是在高效解决一些算法问题中的重要性。具体内容包括：

• 位运算简介：博客首先回顾了基本的位运算符，如按位与（&）、按位或（|）、按位异或（^）、按位非（~）等，并简单解释了它们的作用和应用。
• 位运算的高效性：位运算常常比常规的算术运算（如加法、乘法等）更高效，尤其是在处理大数据量时，它能够显著降低时间复杂度。
• 经典应用场景：博客列举了位运算在一些常见问题中的应用，如判断一个数是否为2的幂、计算一个数的二进制表示中1的个数、交换两个数等。通过这些实例，展示了位运算的实际效果和灵活性。
• 优化与挑战：通过一些算法的优化（如通过异或运算实现加法），博客强调了位运算如何帮助减少计算时间，并简化代码实现。

接下来可以在下篇博客中深入探讨 位运算的更高级应用！！！

2. 题目1：两整数之和

题目链接：371. 两整数之和 - 力扣（LeetCode）

题目描述：

2.1 算法思路：

1. 加法的位运算原理

在计算机中，整数加法通常是通过“位运算”来实现的。加法的基本原理可以分为两个部分：

• 异或运算 (^)：相当于不带进位的加法。
  • a ^ b 计算的是 a 和 b 在每一位上的和，但不考虑进位。也就是说，如果某一位上有 1 和 1，那么这部分结果会变成 0（因为 1 + 1 = 0，不考虑进位）。
• 与运算 (&) 和左移运算 (<<)：计算进位。
  • a & b 找出 a 和 b 中相同位上都为 1 的位置，这些位置就是加法中的进位。
  • << 1 将进位左移一位，因为进位在下一位产生。

2. 算法步骤

1. 异或运算：x = a ^ b 计算不带进位的部分。
2. 计算进位：carry = (a & b) << 1 计算进位，并左移一位，准备与其他位相加。
3. 更新值：
   • 将 a 更新为 x（即当前的和，但不包括进位部分）。
   • 将 b 更新为 carry（即当前的进位）。
4. 重复直到没有进位：当 b（进位）为 0 时，表示加法已经完成，a 就是最终的和。

3. 算法的终止条件

• 这段代码会持续执行直到进位 b 为 0。当 b 为 0 时，表示所有的进位已经被加到结果中，运算结束，a 就是最终结果。

2.2 示例代码：

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;                         // 更新a为不带进位的结果
            b = carry;                     // 更新b为进位
        }
        return a;                          // 当进位为零时，返回结果
    }
};

2.2.1 示例运行

假设 a = 3 和 b = 5，我们来看看具体的执行过程：

• 初始值：
  • a = 3（二进制：0011）
  • b = 5（二进制：0101）
• 第一步：
  • x = a ^ b = 0011 ^ 0101 = 0110（不带进位的和）
  • carry = (a & b) << 1 = (0011 & 0101) << 1 = 0001 << 1 = 0010（进位）
  • 更新 a = 0110，b = 0010
• 第二步：
  • x = a ^ b = 0110 ^ 0010 = 0100（不带进位的和）
  • carry = (a & b) << 1 = (0110 & 0010) << 1 = 0010 << 1 = 0100（进位）
  • 更新 a = 0100，b = 0100
• 第三步：
  • x = a ^ b = 0100 ^ 0100 = 0000（不带进位的和）
  • carry = (a & b) << 1 = (0100 & 0100) << 1 = 0100 << 1 = 1000（进位）
  • 更新 a = 0000，b = 1000
• 第四步：
  • x = a ^ b = 0000 ^ 1000 = 1000（不带进位的和）
  • carry = (a & b) << 1 = (0000 & 1000) << 1 = 0000 << 1 = 0000（进位）
  • 更新 a = 1000，b = 0000
• 结束时，b 为 0，返回 a = 1000，即结果 8。

2.3 多种解法

2.3.1 解法 2：递归法（模拟加法）

我们可以将上述位运算的实现转换为递归的形式，直观地模拟加法的过程。

代码实现：

class Solution {
public:
    int getSum(int a, int b) {
        if (b == 0) {
            return a;
        }
        return getSum(a ^ b, (a & b) << 1);  // 递归调用
    }
};

解析：

• 递归的基本思想与位运算法相同，但将其转化为递归形式。
• 每次递归调用计算当前的和与进位，直到进位为零为止

2.3.2 解法3：加法运算符（暴力法）

虽然题目要求不使用加法运算符，但我们可以直接利用加法运算符进行暴力求解，这种方式主要是为了与其他方法对比。这里先给出一个简单的实现：

代码实现：

class Solution {
public:
    int getSum(int a, int b) {
        return a + b;  // 直接使用加法运算符
    }
};

解析：

这是最简单、最直观的方法，直接利用加法运算符进行计算。但此方法违背了题目不使用加法运算符的要求，仅供参考。

2.3.3 解法 4：模拟机器加法（通过模拟二进制加法）

模拟机器加法（binary addition），也可以通过移位和按位运算来模拟。

代码实现：

class Solution {
public:
    int getSum(int a, int b) {
        while (b != 0) {
            int carry = a & b;  // 计算进位
            a = a ^ b;          // 计算不带进位的和
            b = carry << 1;     // 将进位左移一位
        }
        return a;
    }
};

解析：

• 此解法与 解法 1 类似，不过它是通过模拟机器内部的二进制加法来实现。
• 同样通过位运算来计算进位和和，并通过循环逐步更新直到没有进位。

2.3.4 解法 5：使用模拟加法运算（不使用位运算）

这种方法通过构造一个二进制加法的循环，模拟加法过程。它不直接利用位运算，但思想上是通过借位和进位来实现加法。

代码实现：

class Solution {
public:
    int getSum(int a, int b) {
        int carry = 0;
        while (b != 0) {
            carry = a & b;           // 计算进位
            a = a ^ b;               // 计算不带进位的部分
            b = carry << 1;          // 将进位左移，准备加到下一位
        }
        return a;  // 返回最终结果
    }
};

2.3.5 总结：

• 位运算法（解法 1 和 2）是最常见且高效的解决方案，尤其适用于不使用加法运算符的场景。通过异或和与运算计算不带进位的和与进位部分，直到进位为零。
• 递归法是对位运算的递归封装，与循环方法本质相同，但实现方式更简洁。
• 暴力法（解法 3）直接使用加法运算符，虽然是最简单的解法，但不符合题目的要求。
• 机器加法法（解法 4）是对机器加法的模拟，实际上与位运算法的实现类似，但展示了加法如何在硬件中执行。

这些解法的核心思想几乎都是通过模拟加法的过程来完成加法操作，利用位运算能够在不使用加法符号的情况下高效地计算出结果。

2.4 复杂度分析

2.4.1 时间复杂度

• 每次循环都会减少进位的影响。由于每次操作都会消除掉至少一位的进位，循环的次数最多为 32 次（对于 32 位整数）。因此，时间复杂度为 O(1)，即常数时间复杂度。

2.4.2 空间复杂度

• 算法仅使用了几个变量（x, carry 等），空间复杂度是 O(1)。

2.5 总结

这段代码利用了位运算模拟了整数的加法过程，通过不断计算“和”和“进位”来得到最终结果，避免了直接使用加法运算符 +。

3. 题目2：只出现一次的数字 ||

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

题目描述：

3.1 算法思路：

解法思路：利用位运算

为了高效地解决这个问题，我们可以利用 位运算。以下是该解法的详细思路和步骤：

1. 问题核心： 所有元素都出现 3 次，意味着它们的每一位在整个数组中出现的次数一定是 3 的倍数。唯一的那个元素，它在某些位上出现的次数不是 3 的倍数（而是 1 次）。
2. 逐位统计： 我们逐位检查每个数的二进制表示，从最低位开始统计每一位的总和。如果某一位的总和不是 3 的倍数，说明该位属于唯一出现一次的元素。
3. 算法步骤：
   • 遍历数组中的每一个数，按位统计每一位上 1 的个数。
   • 如果某一位上 1 的个数不是 3 的倍数，说明该位在出现一次的数上是 1，否则是 0。
   • 最后通过按位或操作将每一位的结果合成最终的结果。

3.2 示例代码：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;  // 最终结果，保存唯一的那个数
        // 遍历每一位，从第0位到第31位
        for (int i = 0; i < 32; ++i) {
            int total = 0;
            // 遍历所有数字，统计第i位上1的个数
            for (int num : nums) {
                total += ((num >> i) & 1);  // 将num的第i位右移到最低位，并与1做与运算
            }
            // 如果该位的1的个数不是3的倍数，说明该位属于唯一出现的数字
            if (total % 3) {
                ans |= (1 << i);  // 将结果的第i位设置为1
            }
        }
        return ans;  // 返回唯一出现一次的数字
    }
};

3.2.1 详细解析

1. 初始化：

int ans = 0;

• ans 用于保存最终结果，即唯一出现一次的元素。初始时将其设置为 0。

2. 遍历每一位

for (int i = 0; i < 32; ++i) {

我们从第 0 位开始，到第 31 位（假设整数是 32 位）。对于每一位，我们都要计算所有数字在该位上的总和。

3. 统计每一位的 1 的个数

int total = 0; for (int num : nums) { total += ((num >> i) & 1); }

• 对于每个数 num，首先将 num 右移 i 位：num >> i，这样我们就可以把第 i 位移到最低位。然后通过 & 1 获取该位的值（1 或 0）。
• total 统计的是数组中所有数字的第 i 位上 1 的个数

4.判断是否是 3 的倍数：

if (total % 3) { ans |= (1 << i); }

• 如果该位的 1 的个数不是 3 的倍数，说明在唯一出现的数字中，这一位是 1（因为其他所有数字的该位是 3 次出现的 1 和 0）。
• ans |= (1 << i)：通过 |= 操作，将 ans 的第 i 位设置为 1。

5. 返回结果：

return ans;

1. 遍历完所有的 32 位后，ans 就包含了唯一出现一次的数字。

3.3 多种解法

3.3.1 解法 2：使用哈希表

另一种方法是使用 哈希表 来记录每个数字出现的次数。由于题目给定了数字只会出现 1 次或 3 次，我们可以利用这一点来优化。

具体步骤：

1. 使用哈希表统计每个数字出现的次数。
2. 遍历哈希表，返回出现次数为 1 的那个数字。

代码实现：

#include <unordered_map>

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        for (auto& entry : count) {
            if (entry.second == 1) {
                return entry.first;
            }
        }
        return 0;  // 默认情况（理论上不会到这里）
    }
};

复杂度分析：

• 时间复杂度：O(n)，我们需要遍历数组中的所有元素，且哈希表的操作是常数时间复杂度。
• 空间复杂度：O(n)，哈希表需要存储所有数字。

优点：

• 实现简单，直观。
• 哈希表可以高效地解决问题。

缺点：

• 空间复杂度较高，因为需要额外的存储空间来存储数字出现的次数。

3.3.2 解法 3：位运算（模拟三数求和）

通过位运算模拟三数求和的方法是本题的经典解法，它基于一个重要的观察：所有数字都出现 3 次，唯一数字出现 1 次，可以通过位运算来达到目的。这里我们用一个更巧妙的方法来处理进位。

具体步骤：

1. 使用两个变量 ones 和 twos 来分别记录每个二进制位出现 1 的次数。
   • ones：表示那些出现 1 次的二进制位。
   • twos：表示那些出现 2 次的二进制位。
2. 通过按位与、按位异或等操作来更新 ones 和 twos，确保最终 ones 中保存的就是唯一出现一次的数字。

代码实现：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (int num : nums) {
            twos |= ones & num;    // 如果某个位已经在 ones 中并且 num 的该位为 1，那么就把它加到 twos 中
            ones ^= num;           // 将 num 加到 ones 中，意味着 num 的每一位都需要在 ones 中更新
            int threes = ones & twos; // 如果某个位在 ones 和 twos 中都出现，说明它出现了 3 次
            ones &= ~threes;         // 将 threes 中的 1 从 ones 中去除
            twos &= ~threes;         // 将 threes 中的 1 从 twos 中去除
        }
        return ones; // 最终结果在 ones 中，表示唯一出现一次的数字
    }
};

复杂度分析：

• 时间复杂度：O(n)，我们遍历每个元素一次。
• 空间复杂度：O(1)，我们只使用了常数空间。

优点：

• 该解法避免了额外的空间使用，空间复杂度为 O(1)。
• 位运算实现高效，时间复杂度为 O(n)。

缺点：

• 位运算的实现较为复杂，需要一定的理解和推理。

3.3.3 总结

常见解法：

1. 位运算（按位统计）：通过统计每一位 1 的出现次数来解决问题，时间复杂度 O(n)，空间复杂度 O(1)。
2. 哈希表：利用哈希表统计每个数字出现的次数，空间复杂度较高，时间复杂度为 O(n)。
3. 位运算（模拟三数求和）：通过使用 ones 和 twos 变量来模拟出现次数为 1 和 2 的情况，最后保留出现一次的数字，时间复杂度 O(n)，空间复杂度 O(1)。

3.4 时间复杂度与空间复杂度

• 时间复杂度：
  • 遍历每个数字的每一位，共有 32 位，因此时间复杂度为 O(n * 32)，其中 n 是数组的大小。由于 32 是常数，所以可以简化为 O(n)。
• 空间复杂度：
  • 我们只使用了常数空间来存储 total 和 ans，因此空间复杂度是 O(1)。

3.5 总结

这段代码通过位运算高效地解决了在一个数组中找出唯一元素的问题，其他元素都出现了 3 次。核心思想是通过统计每一位上 1 的个数，利用模 3 的特性来判断该位上是否属于唯一出现的数字。

4. 题目3：面试题17.19. 消失的两个数字

题目链接：面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

题目描述：

4.1 算法思路：

1. 异或运算的性质

异或（^）运算具有以下几个特性：

• a ^ a = 0：两个相同的数字异或结果是 0。
• a ^ 0 = a：任何数与 0 异或结果是该数本身。
• 交换性：a ^ b = b ^ a。
• 结合性：(a ^ b) ^ c = a ^ (b ^ c)。

因此，异或是一个非常有效的工具，它能够帮助我们通过 nums 数组和所有从 1 到 n+2 的数字的异或结果来找出缺失的两个数字。

2. 计算所有数字的异或结果

首先，我们将数组 nums 中的所有元素与从 1 到 n+2 的所有数字进行异或操作。因为我们知道有两个数字 a 和 b 是缺失的，那么 ret = a ^ b，即 ret 是这两个缺失数字的异或结果。

3. 提取最低有效位（LSB）

在得到 ret = a ^ b 之后，a 和 b 必然有至少一个二进制位不同。为了进一步分离这两个数字，我们可以利用 ret 中的最低有效位（LSB）。这个位是 a 和 b 在二进制表示中唯一的不同位。通过计算 ret & (-ret)，我们能够找到这个最低有效位（lsb）。

4. 分组操作

根据 lsb 位，我们可以将所有数字（包括 nums 数组中的数字和从 1 到 n+2 的数字）分为两组：

• 第一组：lsb 位为 1 的数字。
• 第二组：lsb 位为 0 的数字。

然后，我们对这两组数字分别进行异或，最后我们得到的两个结果就是缺失的两个数字。

4.2 代码实现

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size();
        int ret = 0;

        // Step 1: 计算 nums 中的元素与 1 到 n+2 之间的数字的异或
        for (auto num : nums) {
            ret ^= num;  // 将 nums 中的数字进行异或
        }
        for (int i = 1; i <= n + 2; i++) {
            ret ^= i;  // 将 1 到 n+2 之间的数字进行异或
        }

        // Step 2: 找到 ret 中最低有效位 (lsb)
        int lsb = ret & (-ret);  // 获取最低有效位

        // Step 3: 分组并计算
        int type1 = 0, type2 = 0;
        
        // 处理 1 到 n+2 中的数字
        for (int i = 1; i <= n + 2; i++) {
            if ((i & lsb) != 0) {
                type1 ^= i;  // lsb 位为 1 的数字
            } else {
                type2 ^= i;  // lsb 位为 0 的数字
            }
        }

        // 处理 nums 数组中的元素
        for (auto num : nums) {
            if ((num & lsb) != 0) {
                type1 ^= num;  // lsb 位为 1 的数字
            } else {
                type2 ^= num;  // lsb 位为 0 的数字
            }
        }

        return {type1, type2};  // 返回缺失的两个数字
    }
};

4.2.1 详细步骤解析

1. 计算 ret： 我们首先计算 ret，它是 nums 数组中的数字与从 1 到 n+2 的数字的异或结果。因为缺失的两个数字 a 和 b，所以 ret = a ^ b。

for (auto num : nums) { ret ^= num; // 将 nums 中的数字进行异或 } for (int i = 1; i <= n + 2; i++) { ret ^= i; // 将 1 到 n+2 之间的数字进行异或 }

2. 计算最低有效位 lsb： ret 是 a ^ b，所以它的二进制表示中，至少有一个位置 a 和 b 不同。我们通过 ret & (-ret) 来找到最低有效位（lsb）。lsb 是 ret 中最右边的 1。

int lsb = ret & (-ret); // 获取最低有效位

3. 分组并计算： 接下来，我们根据 lsb 将所有数字分成两组：

• 组 1：lsb 位为 1 的数字。
• 组 2：lsb 位为 0 的数字。

对每组数字分别进行异或操作，得到的结果就是两个缺失的数字。

int type1 = 0, type2 = 0; // 处理 1 到 n+2 中的数字 for (int i = 1; i <= n + 2; i++) { if ((i & lsb) != 0) { type1 ^= i; // lsb 位为 1 的数字 } else { type2 ^= i; // lsb 位为 0 的数字 } } // 处理 nums 数组中的元素 for (auto num : nums) { if ((num & lsb) != 0) { type1 ^= num; // lsb 位为 1 的数字 } else { type2 ^= num; // lsb 位为 0 的数字 } }

4. 返回结果： 最后，我们返回两个缺失的数字。

return {type1, type2}; // 返回缺失的两个数字

4.3 多种解法

4.3.1 解法 2：使用数学公式

思路：

我们可以利用数列的求和公式来解决这个问题。具体方法如下：

1. 计算理论上完整的数组 [1, 2, ..., n] 的和，记为 sum1，使用公式： sum1=n(n+1)/2
2. 计算实际数组 nums 的和，记为 sum2。
3. 两者的差值 sum1 - sum2 即为缺失的两个数字的和 S： S=x+y 其中 x 和 y 是缺失的两个数字。
4. 再计算这两个数字的平方和的差值。理论上完整的数组的平方和为： sum1_square = 1^2 + 2^2 + ... + n^2 同理，计算实际数组 nums 的平方和 sum2_square。
5. 两者的平方和差值 sum1_square - sum2_square 等于： x2+y2x^2 + y^2x2+y2
6. 通过联立方程来解出缺失的两个数字 x 和 y。

代码实现：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        long long sum1 = (long long)n * (n + 1) / 2;
        long long sum2 = 0;
        long long sum1_square = (long long)n * (n + 1) * (2 * n + 1) / 6;
        long long sum2_square = 0;

        for (int num : nums) {
            sum2 += num;
            sum2_square += (long long)num * num;
        }

        long long diff_sum = sum1 - sum2;  // x + y
        long long diff_square = sum1_square - sum2_square;  // x^2 + y^2

        long long sum = diff_sum * diff_sum - diff_square;
        long long x_plus_y = diff_sum;
        long long x_minus_y = sqrt(sum);  // Use quadratic equation

        int x = (x_plus_y + x_minus_y) / 2;
        int y = x_plus_y - x;
        
        return {x, y};
    }
};

时间复杂度：

• 计算 sum1, sum2, sum1_square, sum2_square 的时间复杂度是 O(n)，因为需要遍历整个数组。
• 计算差值 x + y 和 x^2 + y^2 的时间复杂度是常数时间 O(1)。
• 总的时间复杂度是 O(n)。

空间复杂度：

• 我们只用了常数空间来存储一些变量，所以空间复杂度是 O(1)。

4.3.2 解法3：排序 + 线性扫描

思路：

我们可以通过排序数组后，线性扫描找到缺失的两个数字。具体步骤如下：

1. 将 nums 排序。
2. 遍历排序后的数组，检查数组中缺失的位置。
3. 根据索引位置和实际数字判断缺失的两个数字。

代码实现：

class Solution {
public:
    vector<int> missingTwo(vector<int>& nums) {
        int n = nums.size() + 2;
        vector<int> result;
        sort(nums.begin(), nums.end());

        int expected = 1;
        int i = 0;
        while (i < nums.size()) {
            if (nums[i] != expected) {
                result.push_back(expected);
                if (result.size() == 2) break;
            } else {
                i++;
            }
            expected++;
        }

        // 处理剩余的缺失数字
        if (result.size() < 2) {
            result.push_back(expected);
        }

        return result;
    }
};

时间复杂度：

• 排序的时间复杂度为 O(n log n)，线性扫描的时间复杂度是 O(n)。
• 总时间复杂度为 O(n log n)。

空间复杂度：

• 使用了排序，因此空间复杂度为 O(1)（如果使用原地排序）。

4.3.3 总结

1. 数学方法：通过求和和平方和的差异，利用方程解出两个缺失的数字，时间复杂度 O(n)，空间复杂度 O(1)。
2. 异或方法：利用异或运算的性质，分组计算，时间复杂度 O(n)，空间复杂度 O(1)。
3. 排序 + 扫描：先对数组排序，然后线性扫描找缺失的数字，时间复杂度 O(n log n)，空间复杂度 O(1)。

4.4 时间复杂度与空间复杂度

• 时间复杂度： O(n)，其中 n 是 nums 数组的大小。我们需要遍历一次 nums 数组和从 1 到 n+2 的所有数字，所以时间复杂度是线性的。
• 空间复杂度： O(1)，我们只用了常数的额外空间来存储一些临时变量，因此空间复杂度是常数级别的。

4.5 总结

这个算法通过异或运算和最低有效位（lsb）分组来有效地找出缺失的两个数字，时间复杂度为 O(n)，空间复杂度为 O(1)，是一个高效且简洁的解决方案。

5. 总结

• 异或运算：
  • 异或是解决这类问题的常见技巧，特别适用于找到数组中唯一的、缺失的或者出现异常次数的元素。
  • 异或满足自反性和交换律，非常适合用来消除重复的数字或找到不重复的元素。
• 数学公式：
  • 数学方法特别适用于基于数字和、平方和等计算，可以通过比较理论和实际结果来快速推导缺失的数字。
• 分治法和位运算：
  • 通过位运算（如最低有效位的分类）可以有效分组，进而逐步缩小问题的范围，最终得到缺失的数字。

6. 最后

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

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

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