位运算符之异或

按位运算符 – 异或（^）

1. 按位运算符

按位运算符对整数值的位进行操作。例如，左移运算符将位向左移，按位非运算符将所有的1变成0，所有的0变为1，C++共有6个这样的运算符：<<、>>、~、&、|、^。今天我们来介绍其中一种，异或运算符（^）.

2. 按位异或运算符

异或（^）运算符在两个运算对象上逐位执行相应的逻辑操作：

size_t b1 = 10;// 00001010
size_t b2 = 15;// 00001111
	   b1 ^ b2;// 00000101

对于位异或运算符（^）来说，如果两个运算对象的对应位置有且只有一个为1，则运算结果中该位为1，否则为0。可以理解为“相同为0，相异为1”。

3. 性质

异或运算有以下三个性质：

1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a ^ 0 = a。
2. 任何数和其自身做异或运算，结果是 0 ，即 a ^ a = 0。
3. 异或运算满足交换律和结合律，即 a ^ b ^ a = b ^ a ^ a = b ^ (a ^ a) = b ^ 0 = b。

4. 例题

只出现一次的数字

解题思路：

假设数组中有 2m+1个数，其中有 m 个数各出现两次，一个数出现一次。令 a₁、a₂、 a₃、……、 a_m、为出现两次的 m 个数，a_m+1为出现一次的数。

根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：

(a₁ ^ a₁) ^ (a₂ ^ a₂) ^ …… ^ (a_m ^ a_m) ^ a_m+1

根据性质 2 和性质 1，上式可化简和计算得到如下结果：

0 ^ 0 ^ …… ^ 0 ^ a_m+1= a_m+1

因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) 
        {
            ret ^= e;
        }
        return ret;
    }
};