在算法面试与编程挑战中，有一道极为经典的题目经常出现：给定一个整数数组，其中只有一个数字出现了奇数次，其余数字均出现偶数次，要求找出这个出现奇数次的数。进一步升级的问题是，如果数组中有两个数字出现了奇数次，其他数字都是偶数次，又该如何求解？两个问题均设定了严格的时间与空间限制——必须满足时间复杂度 O(N)，额外空间复杂度 O(1)。
题目
给定一个整型数组 arr，其中只有一个元素出现了奇数次，其余元素均出现偶数次，请输出这个出现奇数次的数。
进阶
有两个数出现奇数次，其他所有数均出现偶数次，需要输出这两个出现奇数次的数。
难度与要求
本题难度为中等。要求时间复杂度 O(N)，额外空间复杂度 O(1)。
解答
首先需要明确异或运算的一个基本性质：任何整数 n 与 0 进行异或（XOR）运算的结果为 n，而 n 与自身异或的结果为 0。此外，异或运算满足交换律和结合律。基于这些特性，我们可以设计出极其简洁的解法。
对于只有一个数出现奇数次的场景，先声明一个整型变量 eO，并初始化为 0。然后遍历整个数组，让 eO 与每个数执行异或操作（eO = eO ^ 当前数）。遍历结束后，eO 的值就是那个出现奇数次的数。为什么这种方法有效？因为异或运算满足交换律和结合律，数组中所有出现偶数次的数在异或过程中会成对抵消为 0，最终只留下出现奇数次的数。举例说明：假设 A、B、C 各出现偶数次，D 出现奇数次，无论以何种顺序进行异或，结果都等同于先连续异或所有 A，再连续异或所有 B，依此类推，最后异或 D。偶数次的数抵消后结果为 0，最终结果就是 D。因此，只要数组中仅有一个数出现奇数次，无论元素顺序如何，最终的 eO 就是该数。对应的实现方法可参考 printOddTimesNum1。
对于有两个数出现奇数次的场景，设这两个数分别为 a 和 b。第一轮遍历后，eO 的值等于 a ^ b，且该结果一定不为 0。由于 eO 非零，其 32 位二进制表示中至少有一位是 1。假设第 k 位为 1，这意味着 a 和 b 在第 k 位上一个为 1、另一个为 0。接下来再设置一个变量 eOhasOne 并初始化为 0，进行第二次遍历。在第二次遍历中，只对第 k 位为 1 的数进行异或，忽略第 k 位为 0 的数。这样，第二次遍历结束后，eOhasOne 就是 a 或 b 中的某一个，而 eO ^ eOhasOne 的结果即为另一个出现奇数次的数。该思路的核心在于利用某一位的差异将两个数划分到不同的子集中，再分别进行异或操作。
package live.every.day.ProgrammingDesign.CodingInterviewGuide.BitwiseOperation;
/**
* 在其他数都出现偶数次的数组中找到出现奇数次的数
*
* 进阶版：找到两个出现奇数次的数
*/
public class InOtherNumAppearEvenArrayFindAppearOddNum2 {
public static void printOddTimesNum2(int[] arr) {
int eO = 0, eOhasOne = 0;
for (int curNum : arr) {
eO ^= curNum;
}
int rightOne = eO & (~eO + 1);
for (int cur : arr) {
if ((cur & rightOne) != 0) {
eOhasOne ^= cur;
}
}
System.out.println(eOhasOne + " " + (eO ^ eOhasOne));
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 3, 2, 8, 1, 6};
printOddTimesNum2(arr);
}
}
// ------ Output ------
/*6 8*/整体思路非常清晰：首先利用异或运算的交换律和结合律消除所有出现偶数次的数，再通过定位二进制位上的差异来分离两个出现奇数次的数。代码实现简洁高效，是位运算在实际问题中的经典应用案例。
