【位运算经典应用】 寻找那个唯一的数
Single Number
这一系列有三道题，第一题也是最简单最经典的。
有一个数组，里面的元素每个都出现了两次，除了一个特殊的，求这个特殊元素。接触过这类题目的coder很快能够脱口而出：直接异或就ok了！的确如此：
var singleNumber = function(nums) { return nums.reduce(function(pre, item) { return pre ^ item; });};但是为何这样能得到答案？我们假设有个数组[1, 2, 3, 1, 2]，很显然我们要找出3这个元素。我们首先将数组元素全部用二进制表示：
0 11 01 10 11 0我们从右往左，按位分析。如果数组中所有元素全部都是出现两次，那么每一位上的1的数量之和肯定是2的倍数。我们看从右往左的第一位，1出现了三次，这多出的一次就是3的起作用，从右往左数第二位，1同样出现了三次，同样是因为3的原因。所以我们可以得到该元素的二进制表示为11，也就是3。
继续思考，我们似乎需要这么一种“加法”运算，使得每位上的 1 bit 数量能够得到累积，但是累积到2了就能清零。幸运的是，^运算符就是我们要找的。
于是代码也就很好理解了。
Single Number II
这是上题的加强版，数组中每个元素都出现三次，除了一个特殊的，找出这个特殊元素。
我们以数组[1, 2, 3, 1, 2, 1, 2]举例，将数组元素用二进制表示：
0 11 01 10 11 00 11 0如果理解了上题，此题的思路似乎也就呼之欲出了。我们也可以按位运算，计算1 bit的数量，如果每个数字都出现三次，那么每位上的1 bit数量肯定是3的倍数，相反如果不是3的倍数，那么就是那个特殊的数在捣蛋。
我们似乎需要这么一种“加法”运算，使得每位上的 1 bit 数量能够得到累计，并且累计到了3就自动清零。但是理想是美好的，现实是残酷的，并没有这样一种神奇的运算（三进制？）。
但是我们可以用一个数“辅助”，因为每一位的1 bit数量统计都是类似的，所以假设正在统计某一位的1 bit数量。我们用a来表示 1 bit 的数量，当 1 bit 的数量为0时，a=0；当数量为1时，a=1；当数量为2时，a=2？非也，位运算只能表示0和1，所以这时我们引进第二个变量b，我们用b=1来代表已经有了2个 1 bit，所以当有两个 1 bit 时，a=0,b=1。数量统计结果逢3化0，所以只有0、1、2三种结果：
bits数量 a b 0 0 0 1 1 0 2 0 1思路也就显而易见了，每次运算我们维护a和b的值，运算到最后即可得到结果：
var singleNumber = function(nums) { var a = 0, b = 0; nums.forEach(function(item) { b = a & (b ^ item); a = b | (a ^ item); }); return a;};当然最朴素的做法是按位枚举每一位的 1 bit 的数量。
Single Number III
还是一个数组，每个元素出现两次，只有两个特殊的元素出现一次，把这两个特殊的元素找出来。
两个特殊的元素？这时候直接异或也并没有什么卵用了啊...以数组[1, 1, 2, 2, 3, 3, 4, 5]举例，如何把4和5找出来？一个数组中有两个特殊的数字，不能用异或运算得到结果，如果只有一个了呢？没错，我们可以把4和5根据某一规则分到两个数组中，然后在各自数组中进行异或从而得到结果。
那么如何分配？我们把4和5用二进制表示出来看看：
1 0 01 0 1因为两个数字不相同，所以它们的二进制码肯定有一位是不同的。我们只需找出这一位，然后根据这一位上是0是1，将数组所有元素分到两个新的数组中，这时4和5肯定已经被分到了不同的数组中，而其余两个相同的数字肯定在一个数组中，这时就能分别对两个数组进行异或运算了。
关于这一位，可以找右数第一个不同位，把两数异或找出右边第一个1即可，而两数的异或其实就是原数组所有元素的异或。
var singleNumber = function(nums) { var tmp = nums.reduce(function(pre, item) { return pre ^ item; }); var one = tmp & (-tmp); // 取右数第一位1 var a = [], b = []; nums.forEach(function(item) { item & one ? a.push(item) : b.push(item); }); return [ a.reduce(function(pre, item) { return pre ^ item; }), b.reduce(function(pre, item) { return pre ^ item; }) ];};
