找两个单身狗（^的使用应用)（从右向左数第一个为 1 的比特位）

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

问题描述：

给定一个数组，其中除了两个数字之外，所有其他数字都出现了两次。我们的任务是找出这两个只出现一次的数字。

例如，给定数组：

csharp[1, 2, 3, 4, 5, 1, 2, 3, 4, 6]

其中，5 和 6 只出现了一次，其他数字都出现了两次。我们的目标是通过编程找出这两个数字。

解题思路：

1. 利用异或运算的性质

我们可以利用 异或运算 来解决这个问题。异或运算有以下几个重要的性质：

• a ^ a = 0：两个相同的数字异或，结果是0。

• a ^ 0 = a：任何数字与0异或，结果是它本身。

• 异或运算是交换律和结合律的，意味着 a ^ b ^ c 与 a ^ c ^ b 结果相同。

由于数组中除了两个数字外，其它数字都出现两次，所以通过异或运算，最终我们可以将所有出现两次的数字都消掉，留下这两个只出现一次的数字。

2. 为什么异或所有数字能得到最终的结果？

假设我们有一个数组 [a, b, c, a, b, c, d, e]，其中除了 d 和 e 外，所有数字都出现了两次。通过异或所有数字，我们得到以下结果：

nginx

a ^ b ^ c ^ a ^ b ^ c ^ d ^ e = (a ^ a) ^ (b ^ b) ^ (c ^ c) ^ d ^ e

由于任何数字与自己异或结果为0，所以 (a ^ a) = 0，(b ^ b) = 0，(c ^ c) = 0。因此最终结果是：

0 ^ 0 ^ 0 ^ d ^ e = d ^ e

这说明最终结果 d ^ e 是两个只出现一次的数字异或的结果。

3. 如何从 d ^ e 找到 d 和 e？

d ^ e 的结果告诉我们 d 和 e 在二进制上有不同的某一位（至少有一位是1）。通过分析 d ^ e 的结果，我们可以找出一个位，确保 d 和 e 在这一位上不同。然后，基于这个位，将数组分成两组，分别找出 d 和 e。

4. 实际操作步骤：

• 第一步：计算数组中所有数字的异或结果，得到 d ^ e。

• 第二步：找到 d ^ e 中任意一位为1的比特（这是 d 和 e 在该位置上的不同）。假设我们找到的是第 k 位。

• 第三步：将数组中的所有数字根据该位是否为1分为两组：一组是该位为1的数字，另一组是该位为0的数字。

• 第四步：分别对这两组数字做异或操作，最终得到 d 和 e。

详细步骤和代码实现：

第一步：计算所有数字的异或结果

我们首先对数组中的所有数字进行异或操作，得到 d ^ e。

for (int i = 0; i < n; i++)

{
        xorResult ^= arr[i];

 }

第二步：找到不同的比特位

接着，我们可以通过 d ^ e 的结果找到 d 和 e 在某一位上的差异。我们可以通过 d ^ e 的二进制表示来找到这一位：d ^ e & (-d ^ e)。

int rightmostBit = xorResult & (-xorResult); // 获取最右边的 1 位
这一行代码在位运算中非常有用，它的目的是 提取 xorResult 中最右边的 1 位，这在后续的步骤中帮助我们将数组中的数字分为两组，从而找出两个只出现一次的数字。

为什么需要提取最右边的 1 位？

通过 xorResult，我们已经知道数组中有两个数字 d 和 e 只出现一次，其余的数字都成对出现，异或的结果是这两个数字的异或。由于这两个数字一定在某些比特位上是不同的，利用这一点，我们可以将这两个数字分到不同的组中。为了分组，我们需要找出 xorResult 中某一位上的差异，而最简单的方法就是找到 最右边的 1 位。

如何理解 xorResult & (-xorResult)：

        int num1 = 0, num2 = 0;

第三步：根据该位分组

xorResult 是两个只出现一次的数字异或的结果，它的二进制表示中至少有一个位是不同的。我们选择 rightmostBit 这个比特位，是因为它是 d 和 e（那两个只出现一次的数字）之间的一个不同的比特位。

利用该位分组，分为两组：

• 一组是该位为1的数字。

• 一组是该位为0的数字。

我们将整个数组的元素分为两组：一组是该比特位为1的数字，另一组是该比特位为0的数字。我们希望通过这个分组，将两个只出现一次的数字分别归到不同的组里。（每一组只有一个）
    for (int i = 0; i < n; i++) {
        if (arr[i] & rightmostBit) {
            num1 ^= arr[i]; // 该比特位为 1 的数字
        } else {
            num2 ^= arr[i]; // 该比特位为 0 的数字
        }
    }

第四步：对两组进行异或

对这两组数字分别进行异或操作，最终结果分别就是我们要找的两个数字。

 printf("The two numbers that appear only once are: %d and %d\\n", num1, num2);

主函数

int main() {
    int arr[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    findTwoSingleNumbers(arr, n);
    return 0;
}

详细函数

#include <stdio.h>

void findTwoSingleNumbers(int arr[], int n) {
    int xorResult = 0;
    
    // 第一步：计算所有数字的异或结果
    for (int i = 0; i < n; i++) {
        xorResult ^= arr[i];
    }

    // 第二步：找到一个比特位，使得该位在两个只出现一次的数字之间不同
    int rightmostBit = xorResult & (-xorResult); // 获取最右边的 1 位
    
    int num1 = 0, num2 = 0;
    
    // 第三步：将数组中的数字分为两组，根据该比特位为 1 或 0
    for (int i = 0; i < n; i++) {
        if (arr[i] & rightmostBit) {
            num1 ^= arr[i]; // 该比特位为 1 的数字
        } else {
            num2 ^= arr[i]; // 该比特位为 0 的数字
        }
    }

    // 输出结果
    printf("The two numbers that appear only once are: %d and %d\\n", num1, num2);
}

int main() {
    int arr[] = {1, 2, 3, 4, 5, 1, 2, 3, 4, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    findTwoSingleNumbers(arr, n);
    
    return 0;
}