位运算

[lihuakkk]

计算机的本质就是1010，掌握位运算可以帮助我们理解计算机原理。利用位元算的一些特点，对一些题目可以给出更高效的算法。

位操作的资料：MDN 按位操作符

Q: Single Number (problemId: 136)

给一个非空的整数数组，里面的元素只有一个元素出现了一次，其他都是成对出现的，找出那个只出现了一次的元素。

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

解法：

var singleNumber = function(nums) {
    return nums.reduce((result, num) => result ^= num, 0);
};

解释：

a ^ b = b ^ a
(a ^ b) ^ c = a ^ (b ^ c)
a ^ a = 0
a ^ 0 = a
a ^ b ^ b ^ c ^ c = a ^ 0 ^ 0 = a

Q: Sum of Two Integers (problemId: 371)

不使用+和-操作符，计算两个整数之和。

Example 1:

Input: a = 1, b = 2
Output: 3

Example 2:

Input: a = -2, b = 3
Output: 1

解法：

var getSum = function(a, b) {
    return b === 0 ? a : getSum(a^b, (a&b) << 1);
};

解释：

/**
    10101010
  + 01001010

  通过a^b相加对应的比特位，通过a&b获取进位的比特位
*/