本文共 2880 字，大约阅读时间需要 9 分钟。

首先要了解异或运算，异或是一种二进制的位运算，符号以 XOR 或 ^ 表示。

异或的运算规则：

1. 先将运算的数化为二进制
2. 化为二进制对齐，相同位进行异或操作：
   1 ^ 1 = 0
   0 ^ 0 = 0
   1 ^ 0 = 1
3. 再化为10进制
   

异或的性质

（1）交换律： A ^ B = B ^ A

（2）结合律： ( A ^ B ) ^ C = A ^ ( B ^ C )

（3）自反性： A ^ B ^ B = A （由结合律可推： A ^ B ^ B = A ^ ( B ^ B ) = A ^ 0 = A）

由此得出三个重要的结论：

• 0 ^ a = a
• a ^ a = 0
• a ^ b ^ b = a

应用异或的运算解题：

案例一：将数字1-1000存放在一个大小为1001的数组中，其中只有一个数字重复出现两次，找出重复数字

#include
   
    using namespace std;/* 异或方法：该问题为异或自反性的变种题，将数字以二进制形式展示，即可发现其中奥秘。 *      1:                            1 *      2:                         1  0 *      3:                         1  1 *      4:                      1  0  0 *      5:                      1  0  1 *      6:                      1  1  0 *      7:                      1  1  1 *      8:                   1  0  0  0 *      9:                   1  0  0  1 *     10:                   1  0  1  0 *     11:                   1  0  1  1 *     12:                   1  1  0  0 *     13:                   1  1  0  1 *     14:                   1  1  1  0 *     15:                   1  1  1  1 *     16:                1  0  0  0  0 *    .... *   1000: 1  1  1  1  1  0  1  0  0  0 * Repeat: .  .  .  . 64 32 16  8  4  2 *   Flag: A  B  C  D  E  F  G  H  I  J *  * 每一位（列）都有一定的重复间隔，且间隔为偶数； * 在每个重复内，前一半为1，后一半为0，即除了末位（J位）以外，其它位的每个重复异或结果均为0。 * 因此，将1001个整数依次异或运算，最终结果就是重复的数字，相当于重复数字与0进行异或，得到其本身。 */ int main(){
   	// 初始化条件 	int a[1001];	for(int i = 1; i < 1000; i++) a[i - 1] = i;	a[1000] = 5;		// 开始运算	int result = 0;	for(int i = 0; i <= 1000; i++)	{
   		result = result ^ a[i];	}	cout << result;}
   

这个问题还有另外两种解法，一种是把那1001个数加起来减去(1000 + 1) * 1000 / 2， 另一种类似于桶排序的解法：

#include
   
    using namespace std; int main(){
   	int a[1001] = {
   }, b[1001];	for(int i = 1; i <= 1000; i++) b[i - 1] = i;	b[1000] = 5;		for(int i = 0; i <= 1000; i++)	{
   		if(a[b[i]] == 0){
   		    a[b[i]] = 1;		}		else{
   		    cout << b[i] << endl;		    break;			}	}}
   

案例二：一堆数中，只有一个数出现奇数次，其他数都出现偶数次，找到该数

#include
   
    using namespace std;int main(){
   	// 13个数，其中 3 出现奇数次 	int a[13] = {
   1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 4, 5, 5}; 	int b = 0;	for(int i = 0; i < 13; i++)	{
   		b = b ^ a[i];	}	cout << b;	return 0;}
   

案例三(LeetCode 260：只出现一次的数字Ⅲ)：给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

/*    思路：         1.先通过一次异或操作，重复元素会被抵消，最终结果相当于两个单次出现的元素（分别记为one和two）的异或值；        2.由异或规则可知，若两个元素one和two的异或值的某二进制位为1，则表示两个元素在该二进制位上的值不同，即分别为1和0，找到其中一个满足条件（为1）的二进制位（记为bitValue）；        3.根据步骤2找到的二进制位bitValue，可以将原数组分成两个部分，one 和 two 分别在两个部分，而相同的重复元素也会被分到同一个部分（因为其相应的二进制位的值是相同的）；        4.对于两个部分再次进行异或操作，即相当于 排除偶次重复 问题，最终可以得到两个题解。*/vector
   
     singleNumbers(vector
    
     & nums) {
          int sum=0;       for(int num:nums)       sum^=num;       int temp=sum&(-sum);// 取sum最后边的1       int a=0;       int b=0;       for(int num:nums)       {
              if(temp&num)            a^=num;           else           b^=num;       }       return {
   a,b};    }
    
   

转载地址：http://evnqi.baihongyu.com/