异或运算的理解和应用

小鱼儿 2023-07-20 03:25 18阅读 0赞

**异或的运算规则，简单来说，就是当前位的两个二进制的表示不同时为1，相同时则为0。**

百度百科对于[异或][Link 1]的解释如下：

> 异或，英文为exclusive OR，缩写成xor  
> 异或（xor）是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”，计算机符号为“xor”。其运算法则为：  
> a⊕b = (¬a ∧ b) ∨ (a ∧¬b)  
> 如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。  
> …

对于计算机来说，由于所有数都是以二进制的形式储存的，因此包括异或运算在内的各种位运算，都具有极高的效率。  
在撸码时一般讨论的异或为两个数的运算，  
如：`1101 ^ 1001 = 0100 (13 ^ 9 = 4)` **（以Java举例，异或运算的符号为 `^` ）**

而其实一个数也可以单独异或，如：`a = 1010，b = ^a = 1 ^ 0 ^ 1 ^ 0 = 0`  
这种方法通常用来计算数字中1的个数是奇数还是偶数，这里不做讨论。

**异或预算的特点：**

*  任何数异或0，都等于自身；
 *  任何数异或1，都等于自身取反；
 *  任何数异或自身，都等于0；（注意是a ^ a，与上文的^a不同）；
 *  任何数对同一个数异或两次后，都等于自身；

**异或运算的应用(以Java为例)：**

**1.面试题中常见的两个整数变量a,b值的互换(若a = 3, b = 4)**  
方法一：

int temp = a; //temp = 3
    a = b; //a = 4
    b = temp; // b = 3

此方法多产生了一个变量temp。

方法二：

a = a + b; // a = 3 + 4 = 7
    b = a - b; // b = 7 - 4 = 3
    a = a - b; // a = 7 - 3 = 4

此方法 a + b 的值有溢出风险。

**而使用异或运算，则可以完美解决：**

a = a ^ b; // a = 3 ^ 4 = 7
    b = a ^ b; // b = 7 ^ 4 = 3
    a = a ^ b; // a = 7 ^ 3 = 4

**2.力扣 leetcode 第136题，求只出现一次的数字：**

> 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。  
> 输入: \[2,2,1\]  
> 输出: 1  
> 输入: \[4,1,2,1,2\]  
> 输出: 4

这道题使用暴力解法需要两次循环，快速排序的方法复杂度为O(nlogn)，若使用Hash表，时间和空间复杂度均为O(n)。  
而题目最主要的要求是**不使用额外的空间**，而题中提到其它元素**均出现了两次**，所以在这里使用异或运算，利用异或的上文所述特点，便可以轻松解决：

class Solution { 
        public int singleNumber(int[] nums) { 
    		int res = 0;
    		for (int num : nums) { 
    			res = res ^ num;
    			// 此处可以简化，写成 res ^= num
    		}
    		return res;
        }
    }

[Link 1]: https://baike.baidu.com/item/%E5%BC%82%E6%88%96/10993677?fr=aladdin