异或运算交换两数

异或的基本运算法则：一个数和自己异或的结果是0，和0异或的结果是其本身，并且满足交换律和结合律。异或也可以看作是没有进位的加法。例如： a ^ a = 0 和 a ^ 0 = a

1. 交换两个数

int a = 10;
int b = 20;

a = a ^ b; // a = a ^ b
b = a ^ b; // b = a ^ b ^ b = a
a = a ^ b; // a = a ^ b ^ a = b

2. 寻找数组内只有一个数出现奇数次的数，数组内只有两个数出现奇数次的数

public class eor {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 1, 2, 2, 3, 3, 3, 4, 4, 4};
        int[] arr2 = new int[]{1, 2, 3, 3, 4, 4};

        System.out.println(findOnlyOneOddNumber(arr1));
        System.out.println(Arrays.toString(findTwoOddNumber(arr2)));
    }

    // 一个数组中只有一个数出现奇数次，找到这个数
    public static int findOnlyOneOddNumber(int[] arr) {
        int eor = 0;

        for (int j : arr) {
            eor ^= j;
        }

        return eor;
    }

    // 一个数组中两个数出现奇数次，找到这个数
    public static int[] findTwoOddNumber(int[] arr) {
        int eor = 0;
        for (int j : arr) {
            eor ^= j;
        }
        int rightOne = eor & (~eor + 1);

        int onlyOne = 0;
        for (int cur : arr) {
            if ((cur & rightOne) == 1) {
                onlyOne ^= cur;
            }
        }
        return new int[]{onlyOne, eor ^ onlyOne};
    }
}

• 详细解释：

cur & rightOne == 1 这一条件的作用，是通过 rightOne 的值，将数组中的数按位区分开来，以便找到其中一个只出现一次的数。这个条件并不是在检查某个数是否是 1，而是在根据 rightOne 确定的位，对数组中的数进行分组。下面是详细解释：

• rightOne 是通过 eor & (~eor + 1) 计算出来的，它的作用是提取出 eor 二进制表示中最右侧的 1。
• eor 是两个只出现一次的数的异或结果，这意味着在 eor 的二进制表示中，至少有一位是 1，这表示这两个数在这一位上是不同的（一个是 0，一个是 1）。

为什么要用 cur & rightOne？

• rightOne 只在某一位上为 1（其他位都是 0），这代表两个只出现一次的数在这一位上有所不同。
• 通过 cur & rightOne，我们可以把数组中的数分成两组：
  • 第一组：cur & rightOne == 1，即这一位上是 1 的数。
  • 第二组：cur & rightOne == 0，即这一位上是 0 的数。

这两组中的数分别包含了：

• 一个只出现一次的数在第一组中。
• 另一个只出现一次的数在第二组中。

因为其他数都是出现两次的，异或操作会把这些数相互抵消掉，只剩下那两个只出现一次的数之一。

• onlyOne 通过在第一组中异或，最终会得到那一组中的那个只出现一次的数，因为其他数都出现两次会相互抵消。
• 而 eor ^ onlyOne 则通过将 eor 中的异或结果去掉 onlyOne，得到另一个只出现一次的数。

举例说明

假设 arr 为 {1, 2, 3, 3, 4, 4}：

1. 计算 eor:

   • eor = 1 ^ 2 ^ 3 ^ 3 ^ 4 ^ 4 = 1 ^ 2（因为相同的数 3 和 4 异或后为 0，被抵消）。
   • 结果 eor = 1 ^ 2 = 3，即二进制是 11。

2. 计算 rightOne:

   • rightOne = eor & (~eor + 1)，二进制是 11 & 01 = 01，表示最右侧的 1。

3. 根据 rightOne 分组并异或:

   • 对于 cur 是 1 和 2：
     • 1 & rightOne == 1（因为 1 的二进制是 01，最右位是 1）。
     • 2 & rightOne == 0（因为 2 的二进制是 10，最右位是 0）。
   • 所以 1 被放入一个组，2 被放入另一个组。

4. 找到 onlyOne:

   • 由于 1 被放在了满足 cur & rightOne == 1 的组里，onlyOne 就是 1。
   • 而 eor ^ onlyOne = 3 ^ 1 = 2，所以另一个数是 2。

通过这一方式，cur & rightOne == 1 的检查把不同的数分组，从而让异或操作能够分别得到这两个只出现一次的数。