CodeChef MISSP(Chef and Dolls)问题异或解法原理咨询

我在解决CodeChef平台的**MISSP（Chef and Dolls）**问题时，通过统计元素出现次数的方法实现了找出无配对元素的功能，但无法理解另一段使用异或（^=）操作的代码为何能得到正确结果。以下是两段代码、输入输出示例，以及异或解法的原理解释：

异或解法代码 #

#include <stdio.h>
 
int main(void) 
{
    int t,n,a,res;
    scanf("%d",&t);
    while(t--)
    {
        res=0;
        scanf("%d",&n);
        while(n--)
        { 
            scanf("%d",&a);
            res^=a;
        }
        printf("%d\n",res);
    }
    return 0;
}

输入输出示例 #

示例1 #

输入：

1
3
1
2
1

输出：2

示例2 #

输入：

1
9
1
2
3
4
5
1
4
3
2

输出：5

我的统计次数解法代码 #

#include <stdio.h>
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,t[100001]={0},p;
        scanf("%d",&n);
        int d[n];
        for(int i=0;i<n;i++)
        {
            scanf("%d",&d[i]);
            t[d[i]]++;
        }
        for(int i=0;i<n;i++)
        {
            if(t[d[i]]%2==1)
            {
                printf("%d\n",d[i]);
                break;
            }
        }
    }
    return 0;
}

异或解法的核心原理 #

异或解法能生效，完全依赖于异或运算的三个关键性质：

• 任何数与自身异或结果为0：x ^ x = 0
• 任何数与0异或结果为其本身：x ^ 0 = x
• 异或运算满足交换律和结合律：a ^ b ^ c = a ^ c ^ b = (a ^ b) ^ c

结合MISSP问题的场景：题目中除了目标元素外，所有其他元素都出现偶数次。当我们把所有元素依次与初始值为0的res进行异或操作时：

1. 出现偶数次的元素会两两配对异或，最终结果为0（比如1 ^ 1 = 0，2 ^ 2 = 0）
2. 所有这些0再与唯一出现奇数次（1次）的目标元素异或，结果就是目标元素本身（0 ^ 目标元素 = 目标元素）

拿示例1举例，异或过程是：
0 ^ 1 = 1 → 1 ^ 2 = 3 → 3 ^ 1 = 2，最终结果就是无配对的2。

对比统计次数的解法，异或解法不需要额外的数组存储计数，空间复杂度为O(1)，运行效率更高，代码也更简洁。

内容的提问来源于stack exchange，提问作者Arun Kumar Mandal