由一道用“异或运算符”解决的算法问题而引发的思考

题目：给一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现一次的元素。要用线性时间复杂度解决，不占用额外空间。

示例：输入[2,2,1]输出1；输入[4,1,2,1,2]输出4

基础知识：异或运算符。例如2^1的异或运算要先转换成二进制,根据相同为0不同为1得出010^001=011=3

答案代码

深入思考：为什么异或能够解决这道题？源于题目的限制：其余元素仅仅出现两次。这个两次可以拓展成偶数次。我们把该题异或运算过程展示一下。以输入[4,1,2,1,2]为例

异或运算具体展示图

为什么调换数组中的1、2、1、2也是4呢？加入我们单独看异或运算具体展示图的第个位、或者第十位、或者第百位、或者第千位（也就是挑其中一列竖着看），经过偶数个1或者0，其结果保持仍原状。如下图。

偶数个1、0异或运算是0,0再和只有1个二进制0100运算仍是0100，所以最后输出的结果是0100