c - 如何使用 XOR 查找数组中出现次数为奇数的单个元素？

Question

考虑这个问题:

You are given an array containing positive integers. All the integers occur even number of times except one. Find this special integer.

解决方法:

出现次数为奇数的整数将有 0 对或多对和一个单数。所以，如果我们能找到摆脱所有对的方法，那么我们剩下的就是单个数字。现在，什么摆脱了对？提示:想想一个运算符。

XOR 可以解决问题。它为您提供了没有额外内存的 O(n) 解决方案。

int GetSpecialOne(int[] array, int length)
{
    int specialOne = array[0];

    for (int i=1; i < length; i++)
    {
        specialOne ^= array[i];
    }

    return specialOne;
}

我不明白如何通过累加每个元素的 XOR 来减少数组产生特殊整数。它是如何工作的？

Answer 1

之所以有效，是因为 (N xor Q) xor Q = N。

恰好一个整数出现奇数次，因此它将是唯一没有从列表中“消失”的数字。所有其他数字出现的次数都是偶数，所以它们都以 2 为一组出现(可以想象)，所以它们都“消失”了。此外，XOR 之间的“距离”无关紧要:(((N xor Z) xor Q) xor Z) xor Q = N。即使在对之间存在中间 XOR，Z 和 Q 也会“抵消” .