xor
What's xor
异或(xor)是一个数学运算符。它应用于逻辑运算。异或的数学符号为⊕，计算机符号为xor。其运算法则为:
a ⊕ b = (¬a ∧ b) ∨ (a ∧ ¬b)
如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
异或也叫半加运算，其运算法则相当于不带进位的二进制加法:二进制下用1表示真，0表示假，则异或的运算法则为:0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0(同为0，异为1)，这些法则与加法是相同的，只是不带进位，所以异或常被认作不进位加法。
Laws
a ⊕ a = 0.a ⊕ b = b ⊕ a.a ⊕ b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c.d = a ⊕ b ⊕ c可以推出a = d ⊕ b ⊕ c.a ⊕ b ⊕ a = b.- 若x是二进制数
0101，y是二进制数1011,则x⊕y=1110.
小结：只有在两个比较的位不同时其结果是1，否则结果为0 即"两个输入相同时为0，不同则为1"!
Example
部分计算机语言用1表示真，用0表示假，所以两个字节按位异或如下
00000000
00000000
--xor---
00000000
下面是两个二进制数值进行异或计算:
11111111
00000000
--xor---
11111111
两个十进制数值怎么计算异或： 5 ⊕ 3, 5 ⊕ 5, 7 ⊕ 0;
0101:5 0101:5 0111:7
0011:3 0101:5 0000:0
-xor-- -xor-- -xor--
0110:6 0000:0 0111:7
所以，5 ⊕ 3 = 6,5 ⊕ 5 = 0, 7 ⊕ 0 = 7
从上面三个例子中我们应该可以很明显的意识到
xor的一些运算规则以及其特殊的性质。
Exercise
一个整型数组nums里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
Simplify the Problems
如果题目改为，如果一个数组中只有一个数字出现了一次，其他数字全部出现了两次。那我们怎么做呢？
根据我们前面的知识点介绍，xor具有交换率，a ⊕ a = 0，a ⊕ 0 = a，所以我们只要全员xor操作，最终的结果自然就是那个single dog.
Continue thinking
而题目中并不如我们前面简化分析的那样single dog只有一只，整个数组里面有两只…
处理方法是将原数组分成两组，每组里面各有一只single dog，然后分组xor，自然可以得到两个组的唯一single dog是谁。
注意哦，每组里面除了两只
single dog中的其中一只以外，其他都是couple哦～
那么问题来了，我们怎么分组呢？
步骤：
- 对整个数组全员异或，得到两个
single dog的异或值； - 在异或结果中找到任意为
1的位； - 根据这一
位对所有的数字进行分组； - 在每个组内进行异或操作，得到两个数字。
合理性说明： 首先，两个
single自然会被分开，因为这个xor值本身就是他们俩产生的，为1就说明了他们在这位上不等； 其次，每一对couple自然会被分到同一组，因为他俩在每一位上，与1的xor值，要么同为1，要么同为0。
在2.中，是需要用到左移的：div <<= 1。
Code
int* singleNumbers(int* nums, int numsSize, int* returnSize){
int res = 0, a = 0, b = 0, div = 1;
for(int i = 0; i < numsSize; ++i) res ^= nums[i];
while(!(div & res)) div <<= 1;
for(int i = 0; i < numsSize; ++i) {
if(div & nums[i]) a ^= nums[i];
else b ^= nums[i];
}
*returnSize = 2;
int* re = (int *) malloc (sizeof(int) * 2);
re[0] = a, re[1] = b;
return re;
}
More
& (与)
参加运算的两个数据，按二进制位进行“与”运算。
Laws:
0 & 0 = 0;0 & 1 = 0;1 & 0 = 0;1 & 1 = 1;
两位同时为“1”，结果才为“1”，否则为0
0011:3 1101:13
0101:5 0101:5
--&-- --&--
0001:1 0101:5
| (或)
参加运算的两个对象，按二进制位进行“或”运算。
Laws：
0 | 0 = 0;0 | 1 = 1;1 | 0 = 1;1 | 1 = 1;
参加运算的两个对象只要有一个为1，其值为1。
0011:3 1001:9
0101:5 0101:5
--|-- --|--
0111:7 1101:13
