位运算技巧：高效找出数组中只出现一次的两个数字

1. 问题背景与核心思路

第一次遇到"只出现一次的数字 III"这个问题时，我正为某金融系统的交易日志分析模块编写C++优化代码。系统需要从海量交易记录中快速找出异常交易ID——这些ID往往只出现一次，而其他正常ID都成对出现。传统哈希表方法虽然直观，但在处理千万级数据时内存消耗成为瓶颈。

这个问题在LeetCode上编号为260，要求：给定一个整数数组nums，其中恰好有两个元素各出现一次，其余所有元素均出现两次。找出只出现一次的那两个元素。要求时间复杂度O(n)，空间复杂度O(1)。

关键突破点在于：如何在不使用额外存储的情况下，仅通过位运算分离出两个目标数。这需要深入理解异或运算的特性。

2. 位运算基础与解题原理

2.1 异或运算的核心特性

异或(XOR)运算有三大黄金性质：

1. 任何数和0异或等于其自身：a ^ 0 = a
2. 任何数和自身异或等于0：a ^ a = 0
3. 满足交换律和结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

当我们将数组中所有数字异或时，成对出现的数字会相互抵消（性质2），最终结果等同于两个目标数的异或值。例如：

code复制[1,2,1,3,2,5] → 1^2^1^3^2^5 = (1^1)^(2^2)^3^5 = 0^0^3^5 = 3^5

2.2 分离两个目标数的关键技巧

假设两个目标数为a和b，我们已得到xor_result = a ^ b。现在需要分离出a和b，这里需要位运算的一个精妙应用：

1. 找到xor_result中任意一个为1的位（通常取最低位的1），这个位说明a和b在该位不同
2. 根据这个差异位将原数组分成两组：
   • 该位为0的数字组
   • 该位为1的数字组
3. 此时a和b必定分别落在不同组，且各组内其他数字仍然成对出现
4. 分别对两组进行异或运算，最终得到的就是a和b

3. 完整实现与代码解析

3.1 关键步骤实现代码

cpp复制#include <vector>
using namespace std;

vector<int> singleNumber(vector<int>& nums) {
    // 第一步：获取两个目标数的异或结果
    long xor_result = 0;
    for (int num : nums) {
        xor_result ^= num;
    }
    
    // 第二步：找到最右侧的差异位（两种等价写法）
    // 写法1：xor_result & -xor_result
    // 写法2：(xor_result & (xor_result - 1)) ^ xor_result
    long diff_bit = xor_result & -xor_result;
    
    // 第三步：分组异或
    int a = 0, b = 0;
    for (int num : nums) {
        if (num & diff_bit) {
            a ^= num;
        } else {
            b ^= num;
        }
    }
    
    return {a, b};
}

3.2 代码细节解析

1. 使用long类型：避免INT_MIN取负数时的溢出问题。当xor_result为INT_MIN时，-xor_result会溢出，用long更安全。

2. diff_bit的计算：

   • xor_result & -xor_result利用了补码的特性，快速找到最右侧的1
   • 例如：xor_result = 6 (0110)，-6的补码是1010，相与得0010

3. 分组条件：

   • if (num & diff_bit)判断num在差异位是否为1
   • 这个分组标准确保a和b必然被分到不同组

4. 边界情况与性能优化

4.1 特殊输入处理

1. 空输入：题目保证至少有两个元素，实际工程中可加断言
2. INT_MIN处理：这就是为什么使用long类型
3. 所有元素相同：题目保证恰好有两个单一数字

4