异或巧用：Single Number
今天刷leetcode，碰到了到题Single Number。认为解答非常巧妙，故记之。。。
题目：
Given an array of integers, every element appears twice except for one. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
翻译：给定一个整形数组，当中除了一个元素出现一次外，其它元素均出现两次。找到那个出现一次的元素
注意：算法应具有线性时间复杂度。你能不用额外内存实现它么？
思路：通过异或运算实现。
原理：异或运算中，两个二进制位同样取零，不同则取1.
异或特性：
（1）顺序无关：即若有多个元素相异或，则异或元素能够任意交换顺序。不会影响结果
（2）对同样的数异或两次等于没有异或：即相当于+x和-x
故，依据异或特性，从逻辑上能够觉得是数组中同样元素先各自异或。结果为0，而终于剩下的那个元素即为出现一次的元素。Java代码例如以下：
public class Solution { public int singleNumber(int[] nums) { int res = 0; for(int i:nums) { res ^= i; } return res; }}给定1-1000个连续自然数，然后从中任意去掉两个，再打乱顺序。
要求仅仅遍历一次，求出被去掉的两个数（设为x和y）。
步骤：
（1）计算x^y：现将打乱前和打乱后的两个数组（记：数组1和数组2）的全部元素做异或运算，反复的元素会互相抵消，所得终于结果即为x^y
（2）获取x^y中1所在位置并划分。继续异或：因为x和y是不同的整数，所以这两个数的异或结果。转化为二进制的话，至少有一位是1，如果在第3位。
把数组1按第3位是否为0进行划分，划分为两个数组。每一个数组各包括一个被抽取的数。
把数组2也按这个规则划分为两个数组。这样就得到了4个数组。当中两组是第3位为0，另外两组是第3位为1。
把第3位为0的两个数组进行异或就能得到被抽取的一个事。同理把第3位为1的两个数组异或就能得到另外一个被抽取的数