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

1. 问题背景与核心挑战

第一次遇到这个问题是在准备算法面试的时候，当时觉得"找出只出现一次的数字"这种题目应该很简单。直到看到这个变种——其他数字都出现三次，只有一个数字出现一次，才发现事情没那么简单。传统的异或解法在这里完全失效，因为异或的特性是"相同为0，不同为1"，无法处理出现三次的情况。

这个问题的经典描述是：给定一个整数数组nums，其中除某个元素只出现一次外，其余每个元素都恰好出现三次。要求找出那个只出现一次的元素，并且算法应该具有线性时间复杂度和常数空间复杂度。

提示：这个问题在LeetCode上编号为137，是一道中等难度的位运算经典题。

2. 基础解法：哈希表统计

2.1 最直观的思路

当我第一次面对这个问题时，最直接的想法就是用哈希表记录每个数字出现的次数。这个方法虽然简单粗暴，但确实能解决问题：

cpp复制#include <unordered_map>
#include <vector>

using namespace std;

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; // 根据题目描述，这里应该不会执行
}

2.2 复杂度分析

这种方法的时间复杂度是O(n)，因为需要遍历整个数组两次（一次统计，一次查找）。空间复杂度也是O(n)，因为需要存储哈希表。虽然满足了线性时间的要求，但空间复杂度不是常数级的。

注意：在面试中，如果先提出这个解法，面试官通常会追问"能否用O(1)空间解决？"这正是我们需要探索位运算解法的原因。

3. 位运算解法一：逐位统计

3.1 核心思路

既然哈希表解法空间复杂度不理想，我开始思考如何利用位运算的特性。观察到所有数字（除了目标数字）都出现三次，这意味着如果把所有数字的二进制表示逐位相加，那么每一位的和应该是3的倍数（对于目标数字的位会多1或少2）。

具体步骤：

1. 初始化一个32位的数组count，用于统计每一位1出现的次数
2. 遍历所有数字，统计每一位上1的个数
3. 对count数组的每一位取模3，剩下的就是目标数字的二进制表示

3.2 代码实现

cpp复制int singleNumber(vector<int>& nums) {
    int result = 0;
    for (int i = 0; i < 32; ++i) {
        int sum = 0;
        for (int num : nums) {
            sum +