【Hello Algorithm】异或法（上）

异或的概念

异或在书中一般是这么解释的

“ ^ ”的异或指的是二进制中 对应的对应二进制位相同时异或为零 相异时异或为一

但是我这里推荐一种很巧妙的记忆方式

异或就是二进制位无进位相加

我们下面使用一个例子来让大家更好的理解这句话

仔细观察 在上图中我们将对应位的二进制相加

• 如果有进位 则舍去进位
• 如果无进位 则不变

最后就得到了我们异或的结果

异或的两个性质

1. 0 ^ N = N
2. N ^ N = 0

我们一个个推导

首先来看性质一

0的所有二进制位都是0 而任何数加上0都不变 换一种说法也就是无进位 所以说该位不会改变

那么既然所有位都不会改变这个数当然也不会改变

其次是性质二

两个相同的数异或结果肯定为0

首先我们知道两个相同的数 每一位的二进制位肯定都相同 而二进制位一共就两种情况 0或1

• 如果是0 则两位相加之后还是0 不变
• 如果是1 则两位相加之后进位1 舍弃掉 所以说该位还是0

综上 我们就可以推出两个相同的数异或之后为0

最后根据这两个性质我们还能够推出一个重要的性质

如果一堆数字异或 那么无论我们怎么改变这堆数据的顺序 最后的结果都不会变

下面是简单的证明

首先不管是什么数字 它二进制的每个位肯定是确定的 不是0就是1

我们将每个位的所有数字累加起来只有两种结果 奇数还是偶数

我们上面说过 异或实际上就是无进位相加 如果是偶数模上2之后最后的结果会变成0 （进位都被我们舍弃了）

如果是技术模上2之后最后的结果会变成1 （进位都被我们舍弃了）

所以说 不管我们怎么改变顺序 每个位的数字都是不变的 所以说 如果一堆数字异或 那么无论我们怎么改变这堆数据的顺序 最后的结果都不会变

题目一 不使用额外变量交换两个数字

题目要求 不使用额外变量交换两个数字

交换两个数字的值最常用的方法就是申请一个临时变量 然后我们利用这个临时变量进行两个数字的交换

代码表示如下

void swap(int& x , int& y)
  {
    int temp = x;
    x = y;
    y = temp;
  }

但是按照这个题目的意思 我们不能申请临时变量 这个temp是不允许使用的

这里我们可以使用算数的性质来解决这个问题

void swap2(int& x , int& y)                                                                                  
  {                   
     x = x + y;
     y = x - y;
     x = x - y;
  }

下面是运行的代码和结果

void swap2(int& x , int& y)    
{    
   x = x + y;    
   y = x - y;    
   x = x - y;    
}    
int main()    
{    
  int a = 10;    
  int b = 20;    
  swap2(a , b);    
  cout << "a: " << a << endl;    
  cout << "b: " << b << endl;                                                                                  
  return 0;    
} 

结果如下

但是这种解法有一种缺点 有可能会数据溢出

x = x + y;   

如果此时我们的x和y特别大 超过了数据类型所能容纳的数字 就会造成数据溢出从而发生错误 所以说这种解法就是有缺陷的

此时为了防止数据溢出的情况我们就可以使用异或法来解决问题

代码和结果如下

void swap3(int& x , int& y)    
{    
  x = x ^ y;    
  y = x ^ y;    
  x = x ^ y;    
}    
int main()    
{    
  int a = 10;    
  int b = 20;    
  swap3(a , b);                                                                          
  cout << "a: " << a << endl;    
  cout << "b: " << b << endl;    
  return 0;    
}  

结果如下

同时我们的异或法只是改变数据的二进制位的情况 所以说数据绝对不会出现溢出

下面是原理解释 为什么进行三次异或就能够交换两个数的值

注意：

但是这里需要注意的是 如果A值和B值指向同一个空间 此时就不能使用异或法来交换两个值 因为异或之后两个数字百分百变为0

首先我们要知道 两个相同的数字异或是肯定为0的

我们上面进行了三次异或操作 每次异或操作之后只有一个数字变化了

但是如果两个值指向同一个空间 则进行一次异或操作之后该空间的值就会变为0 即两个数字都改变了

所以说使用该方法的时候千万要注意 两个值在计算机中不能使用同一空间

题目二 出现奇数次的数字

leetcode连接

题目要求： 给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

该题目出现于lc136题 题目原文和测试用例如下

此时它要求我们找出一个数组中那个只出现一次的数字 我们第一时间就应该想到异或法

我们异或法是不是有一个性质

N ^ N = 0

也就是说两个相同的数字异或 它们的值为0 当然我们也可以推广一下 偶数个相同的数字异或 它们的值为0

也就是说题目中所有出现偶数次的数字在异或之后都会变成0

然后根据异或法的第二个性质

0 ^ N = N

我们最后那个出现一次的数异或上0 就能得到我们的最终结果了

代码表示如下

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

运行结果如下