位运算技巧：LeetCode 260题解与异或应用

1. 问题背景与核心挑战

在算法面试和编程竞赛中，位运算类问题往往以其简洁高效的特性成为考察重点。今天我们要探讨的这个问题来自LeetCode第260题"只出现一次的数字 III"，它要求我们在一个整数数组中找到仅出现一次的两个数字，同时满足O(n)时间复杂度和O(1)空间复杂度的限制。

这个问题的特殊之处在于：

• 常规的哈希表解法虽然直观，但需要O(n)空间存储元素出现次数
• 简单的遍历统计无法满足空间复杂度要求
• 当数组中只有一个数字出现一次时，可以用异或运算轻松解决，但扩展到两个数字时情况变得复杂

提示：理解这个问题的关键在于认识到异或运算的"消消乐"特性——相同数字异或结果为0，任何数与0异或保持不变。

2. 位运算基础精要

2.1 异或运算的核心性质

异或(XOR)运算在解决这类问题时展现出惊人的威力，主要基于以下几个性质：

cpp复制a ^ a = 0      // 自反性：相同数字异或结果为0
a ^ 0 = a      // 恒等性：任何数与0异或保持不变
a ^ b = b ^ a  // 交换律
a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c  // 结合律

这些性质意味着我们可以通过连续异或操作来"抵消"数组中成对出现的数字，最终留下的就是我们需要找的单独数字。

2.2 补码与位操作技巧

理解补码表示对于处理位运算问题至关重要：

cpp复制// 对于任意整数x：
-x = ~x + 1    // 补码表示
x & (-x)       // 获取x最右边的1

这个技巧在分离两个目标数字时起到关键作用。例如，当x=6(110)时：

• -x = ~110 + 1 = 001 + 1 = 010
• x & -x = 110 & 010 = 010

2.3 实用位运算技巧集锦

以下是一些高频使用的位运算技巧，建议熟记：

cpp复制// 1. 判断奇偶
bool isOdd = (x & 1) == 1;

// 2. 清零最低位的1
x = x & (x - 1);

// 3. 获取最低位的1
int lowbit = x & (-x);

// 4. 判断某一位是否为1
bool bitSet = (x >> k) & 1;

// 5. 设置某一位为1
x |= (1 << k);

// 6. 设置某一位为0
x &= ~(1 << k);

3. 解题思路深度剖析

3.1 从简单情况入手

先考虑简化版问题：数组中只有一个数字出现一次，其他都出现两次。这时解法非常直观：

cpp复制int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int num : nums) {
        result ^= num;
    }
    return result;
}

这个解法利用了异或运算的消去特性——所有成对出现的数字都会相互抵消，最终剩下的就是唯一的单独数字。

3.2 扩展到两个数字的挑战

当有两个单独数字（设为a和b）时，直接异或整个数组会得到a^b。这给了我们部分信息，但如何分离出a和b呢？核心思路是：

1. 通过a^b的结果找到a和b不同的某一位
2. 根据这一位将数组分成两组
3. 在每组中分别应用单数字的解法

3.3 关键步骤实现

步骤1：计算总体异或值

cpp复制long long diff = 0;
for (int num : nums) {
    diff ^= num;
}
// 此时diff = a ^ b

这里使用long long是为了避免整数溢出的问题，特别是处理INT_MIN时。

步骤2：找到区分位

cpp复制diff &= -diff;

这行代码是算法的精髓所在。它通过补码技巧找到diff中最右边的1，这个1的位置就是a和b在二进制表示中第一个不同的位。

步骤3：分组异或

cpp复制vector<int> result(2, 0);
for (int num : nums) {
    if ((num & diff) == 0) {
        result[0] ^= num;
    } else {
        result[1] ^= num;
    }
}

通过这个分组，我们确保：

• a和b被分到不同的组
• 其他成对数字会被分到同一组，异或后相互抵消

4. 代码实现与优化

4.1 完整解决方案

cpp复制class Solution {
public:
    vector<int> singleNumber(vector<int>& nums)