算法总结——异或运算

异或运算

总结总结一些算法，也方便自己回顾，定时更新。

运算规则：相同取0，相异取1

异或算法有三个特征：
1、任何数和0做异或运算，结果仍然是原来的数，即a ⊕ 0 = a。
2、任何数和自身做异或运算时，结果是0，即a ⊕ a=0 。 注意a ⊕ a ⊕ a = a
3、异或运算满足交换律和结合律，即a ⊕ b ⊕ b = b ⊕ a ⊕ b = a ⊕ ( b ⊕ b ) = a ⊕ 0 = a

运用场景： 比如求一组数据中只有一个数字是奇数项其他都是偶数项，怎么找出它，用异或就很方便。

//在这里贴一段伪代码，就是找出唯一的奇数项，满足了时间和空间复杂度
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        //异或运算
        int set=0;
        for(auto iter:nums) set^=iter;
        return set;
            
    }
};
1
2
3
4
5
6
7
8
9
10
11

(ps:大家理解一下思想就好了，不要碰到这种情况时去无脑排序遍历，或者再开n空间复杂度。)