如何用位运算找出数组中仅出现一次的两个数字？

你的思路完全正确！这是解决这类问题最经典的高效位运算方案，咱们来拆解思路并优化代码细节：

问题描述 #

给定一个包含n个元素的数组，其中除两个数字外，其余所有数字均出现两次。请使用位运算找出这两个数字。

核心思路解析 #

你采用的逻辑非常巧妙（时间复杂度O(n)，空间复杂度O(1)），核心步骤是：

• 全局异或：对数组所有元素执行异或操作，最终结果是那两个只出现一次的数字的异或值（相同数字异或会抵消为0，0异或任何数等于该数本身）。
• 定位区分位：找到异或结果中最右侧的置位（即二进制值为1的位）。这个位的意义是：两个唯一数字在该位上的二进制值不同（一个是0，一个是1）。
• 分组异或：根据这个区分位将数组元素分成两组，每组内的元素分别异或，最终两组的结果就是那两个唯一数字。

你的代码分析与优化 #

你的代码逻辑没问题，但在找区分位和分组判断的部分可以更简洁高效：

• 找最右侧置位可以利用补码特性myxor & -myxor直接得到掩码，不用循环计数。
• 分组时直接用掩码和元素做与运算，就能判断该位是否为1，不用每次循环去数二进制位数。

优化后的代码如下：

#include<iostream>
using namespace std;

int main() {
    cout << "Enter the size of array: " << endl;
    int n;
    cin >> n;
    int arr[n];
    cout << "Enter the array elements: " << endl;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 步骤1：全局异或，得到两个唯一数的异或结果
    int xor_result = 0;
    for (int num : arr) {
        xor_result ^= num;
    }

    // 步骤2：获取最右侧置位的掩码（利用补码特性，保留最右侧的1）
    int rightmost_set_bit = xor_result & -xor_result;

    // 步骤3：按区分位分组异或
    int num1 = 0, num2 = 0;
    for (int num : arr) {
        if (num & rightmost_set_bit) {
            // 该位为1的组，异或后得到第一个唯一数
            num1 ^= num;
        } else {
            // 该位为0的组，异或后得到第二个唯一数
            num2 ^= num;
        }
    }

    cout << "The two unique numbers are: " << num1 << " and " << num2 << endl;
    return 0;
}

关键细节说明 #

• xor_result & -xor_result：在二进制补码规则中，一个数的负数等于其按位取反加1，所以这个操作会精准保留最右侧的1，其余位变为0。比如6（二进制110）& -6（二进制...11111010）= 2（二进制10），直接得到区分位的掩码。
• 分组异或的正确性：相同数字的二进制位完全一致，一定会被分到同一组，组内异或会抵消所有重复数字，最终剩下的就是该组对应的唯一数字。

内容的提问来源于stack exchange，提问作者Yashika Khurana