一. 异或运算 ＾
先贴上参考的说明http://artori.us/exclusive-or/：
异或
不介绍什么是异或了，有人叫半加、数学系的叫按位模2加
下文用得到的一些简单的性质
-
x^0 = x且x^x = 0 -
交换律：
x^y = y^x -
结合律：
(x^y)^z = x^(y^z) -
自反性：
x^y^y = x
下面是几个小题目，可以用异或解决，挺有技巧性
交换两个数ab
a = a^b
b = a^b
a = a^b
有意思的是搜索其他异或例子的时候，发现了这篇文章，文章里实现了一个异或交换的算法，和本文主题无关，不过很有意思，函数更多的时候应该只操作值而不是变量。
UPDATE_2013-05-06: 这个，看到云风写了一个利用这个特性做的双向链表，挺好玩，忍不住写过来。
A集合里拿掉数x得到B集合，求x
令XOR(X)表示将X集合内所有的数做异或
XOR(B)^XOR(A) = XOR(B)^XOR(B)^x = 0^x = x
A = (1..10000).to_a
B = A - [1234]
x = (A + B).reduce(&:^)
puts x #1234
via: http://www.javaeye.com/topic/420487
A集合里拿掉数x、y得到B集合，求x和y
首先按上一个的办法可以推导出xor(A)^xor(B) = xor(B)^xor(B)^x^y = 0^x^y = x^y
x^y的二进制结果，第n位为1，说明x和y的第n位不相同
根据第n位是否为0把A里所有的数分成A1和A0两个数组（A1里的数的二进制第n位都是1，A0都是0）
A1和A0应该各包含了a或者b（这样第n位才能异或出1）
同理可以把B分成B1和B0两个数组
可以得到第一个数 x = A1^B1
第二个数可以y = A0^B0，当然也可以用x^y^x求得
另外如果x^y为0，即x == y，令SUM(X)为X集合内所有数求和
(SUM(A) - SUM(B)) / 2 = x
via: http://blog.chinaunix.net/uid-12453618-id-2935334.html
集合A里只有数x出现1次，其余数全都重复出现2次，求x
xor(A) = x^y^y^…^z^z = x^(y^y^…^z^z) = x^0 = x
x = A.reduce(&:^)
集合A里只有数x出现1次，其余数全都重复出现3次，求x
xor的本质相当于“按位模2加”（adding modulo 2），令p1,p2…pn为布尔值，true为1、false为0，(+)表示异或操作。
p1 (+) p2 (+) ... (+) pn == ( p1 + p2 + ... + pn ) % 2
所以只需要实现按位模3加
( p1 + p2 + ... + pn ) % 3
将集合中所有数二进制表示的同一位的0或1相加，最终的和对3去摸，得到的数即是x
如 A = {5, 7, 7, 7}，二进制表示两个数
101
111
111
+ 111
------
434
% 3
------
101
但愿这坨东西能让人看懂
via: http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/BitOp/xor.html
没有^操作时候实现异或，只用&与 |或 ~非
这里的转换有很多，比如下面这个
x ^ y == (~x & y) | (x & ~y)
具体查看维基百科 《Equivalencies, elimination, and introduction》部分，各种公式
实际运用如下：
最近上leetcoude刷题，题目如下
https://leetcode.com/problems/single-number/#/description
这个题目要求找出数组中唯一一次只出现一次的数字（其他数字出现2次），题目本身很简单，但是想要写出O(n)的算法还是需要点技巧的。
这个题目如果是求数组的和，大家都能写出O（n）的实现，只用单纯的遍历相加即可。但若要求出其中唯一单次出现的数字时，便没有这么直观了。不过可以基于相加做一些联想，是否有另外一种运算法则，使得相同的值运算结果为零，不同的值运算结果体现为加？这个联想可能有点莫名其妙，不过熟悉异或运算的基本性质（结合律），将运算看成二进制的运算就能够理解了。异或运算的“半加”特性可以理解为基于二进制的加法，但是不进位，也就是说加法溢出时丢弃进位。联想到题目上就是，相同的两个数异或得0，剩下唯一的一个单个数字与所有成对的结果0异或，得到唯一得数字。
拓展思维，基于不同的场景，如果能够对于场景构思出一种满足结合律得运算方式，那么这个问题就可以使用一个O（n）的算法来解决！