算法-只出现一次的数字.md

前言

作为一名前端工程师，位操作符极少用到，学过的也都忘光了。但是总是在不经意间，有些问题用位操作符解决，而且可以亮瞎人的眼。

只出现一次的数字

leetcode上有道题，如下：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

最先想到的必然是遍历，然后用Map，保存结果。

先给出如下解法：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let res={}
    let result=0
    for(let i=0;i<nums.length;i++){
        if(res[nums[i]]===undefined){
            res[nums[i]]=true
            result+=nums[i]
        } else if(res[nums[i]]===true){
            res[nums[i]]=false
            result-=nums[i]
        }
    }
    return result
};

具体思路是碰到在res这个object中不存在的，让其在res中作为key，并把值设为true，然后与result相加，接着遍历，再碰到这个数的时候，其在res中的是true，将它的值设为false，让后将result减去它，那么最后剩下来的就是只出现一次的数。

解法通过了验证，但是题目中还有一句话：

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

上面的解法，使用了res这个额外空间，那还有什么更好的办法呢？

按位操作符

按位操作符（Bitwise operators） 将其操作数（operands）当作32位的比特序列（由0和1组成），而不是十进制、十六进制或八进制数值。例如，十进制数9，用二进制表示则为1001。按位操作符操作数字的二进制形式，但是返回值依然是标准的JavaScript数值。

下面的表格总结了JavaScript中的按位操作符：

运算符	用法	描述
按位与（ AND）	a & b	对于每一个比特位，只有两个操作数相应的比特位都是1时，结果才为1，否则为0。
按位或（OR）	`a	b`
按位异或（XOR）	a ^ b	对于每一个比特位，当两个操作数相应的比特位有且只有一个1时，结果为1，否则为0。
按位非（NOT）	~ a	反转操作数的比特位，即0变成1，1变成0。
左移（Left shift）	a << b	将 a 的二进制形式向左移 b (< 32) 比特位，右边用0填充。
有符号右移	a >> b	将 a 的二进制表示向右移b(< 32) 位，丢弃被移出的位。
无符号右移	a >>> b	将 a 的二进制表示向右移b(< 32) 位，丢弃被移出的位，并使用 0 在左侧填充。

如上表我们可知，一个数和自身做按位异或操作结果是0。

0101
^
0101
=
0000

任何数和0做按位异或操作结果是自身，

0101
^
0000
=
0101

又由于按位操作符满足结合律，所以我们把这道题给定的数组，依次按位异或，最终的结果就是只出现一次的数字。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNumber = function(nums) {
    let result=0
    for(let i=0;i<nums.length;i++){
        result^=nums[i]
    }
    return result
};