位运算介绍

位运算，即把数字转为二进制后对二进制的一些操作，即对0或1的操作，实际上计算机的加减乘除都是二进制计算的，所有计算在性质上都是位运算，所以掌握位运算可以有效提高算法效率: 时间复杂度同是O(n)时，位运算比普通的哈希表红黑树快得多，对于内存复杂率，基本可以优化到常数级。

常见的位运算

简单的算法举例

只出现过一次的数字

题目：如果有一个数组nums[]，除去一个数字只会出现一次，其他数字均会出现两次，则对所有数字进行异或，最后出现的数字就是只出现一次的数字。

正常第一印象想出来的做法是哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_set<int> s;
        for(auto n:nums){
            if(s.count(n)){
                s.erase(n);
            }else{
                s.insert(n);
            }
        }
        return *s.begin();
    }
};

异或有这样的性质：

1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a⊕0=a。

2. 任何数和其自身做异或运算，结果是 0，即 a⊕a=0。

3. 异或运算满足交换律和结合律，即 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b。

根据以上性质可设计出这样的算法：

v