如何使用XOR查找数组中出现次数奇数的单个元素？ [英] How does using XOR to find a single element with odd number of occurrences in an array work?

问题描述

考虑这个问题：

您将得到一个包含正整数的数组。除了一个以外，所有整数均出现偶数次。找到这个特殊的整数。

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

解决方案：

出现次数为奇数的整数将具有0对或更多对和一个单数。因此，如果我们能够摆脱所有的配对，那么剩下的就是一个数字。现在，什么摆脱了配对？提示：考虑一个运算符。

The integer with the odd number of occurrences will have 0 or more pairs and one single number. So, if we could some how get rid of all the pairs then all we'd be left with is the single number. Now, what gets rid of pairs? Hint: think of an operator.

XOR可以解决问题。它为您提供O（n）解决方案，而无需额外的内存。

XOR will do the trick. Its gives you O(n) solution with no extra memory.

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

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

    return specialOne;
}

我不明白如何通过在每个元素上累加XOR来减少数组产生特殊的整数。

I don't understand how reducing the array by accumulating the XOR on each element produces the special integer. How does it work?

推荐答案

它起作用是因为（N xor Q）xor Q = N。

It works because (N xor Q) xor Q = N.

恰好一个整数出现奇数次，因此它将是唯一一个不会从列表中消失的数字。所有其他数字均以偶数出现，因此它们都以2的组出现（可以想象），因此它们都消失。同样，XOR之间的距离也无关紧要：（（（（N xor Z）xor Q）xor Z）xor Q =N。即使两对之间存在中间XOR，Z和Q也会抵消。

Exactly one integer is present an odd number of times, so it will be the only number not to "disappear" from the list. All other numbers are present an even number of times so they all appear in groups of 2's (conceivably), so they all "disappear". Also, the "distance" between the XORs don't matter: (((N xor Z) xor Q) xor Z) xor Q = N. The Z's and the Q's "cancel out" even though there are intermediate XORs between the pairs.

这篇关于如何使用XOR查找数组中出现次数奇数的单个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！