异或的特性及简单运用（附面试练习题）#数据结构与算法

柔光的暖阳◎ 2024-04-06 12:32 32阅读 0赞

**目录**

异或运算符 ^

特性

字符表述

汉字表述

快速记忆

简单运用

面试练习题：

面试题1

实现思路

实现代码

面试题2

实现思路

实现代码

--------------------

## 异或运算符 ^ ##

### 特性 ###

#### 字母表述 ####

> 0^N=N
> 
> N^N=0
> 
> a^b=b^a (a^b)^c=a^(b^c)

#### 汉字表述 ####

> 零异或任何数都等于零
> 
> 任何数异或他自己都等于零
> 
> 异或过程中，结果与运算先后顺序无关

### 快速记忆 ###

> ………………**异或是“无进位相加”**………………
> 
> 举例：
> 
> 0000 1010
> 
> \+ 0001 0010
> 
> 得 0001 1000

### 简单运用 ###

> 交换：a=甲，b=乙
> 
> a=a^b
> 
> b=a^b
> 
> a=a^b
> 
> 过程：
> 
> 1，a=甲^乙，b=乙
> 
> 2，a=甲^乙，b=甲^乙^乙=甲^0=甲
> 
> 3，a=甲^乙^甲=0^乙=乙，b=甲

## 面试练习题： ##

### 面试题1 ###

> 一组给定的数组，其中“一种数出现了奇数次，其他种数出现了偶数次”  
> 问：时间O(N)，空间O(1)的条件下，找到这个出现了奇数次的数

### 实现思路 ###

> 通过异或的特性来‘消’掉偶数个数的数

### 实现代码 ###

int a = 0, arr[] = {2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 1};
            for (int i : arr)
                a ^= i;
            System.out.println(a);

--------------------

### 面试题2 ###

> 一组给定的数组，其中“两种数出现了奇数次，其他种数出现了偶数次”  
> 问：时间O(N)，空间O(1)的条件下，找到这两个出现了奇数次的数

### 实现思路 ###

> 通过^的特性，消掉出现了偶数次的数，得到a^b(两个奇数相异或)，此时只需要找出a或者b,就可以通过a^b^a=b的特性求出另一个。
> 
> 因为a^b一定不为0
> 
> 所以a^b的二进制数中肯定有一位为1
> 
> 因为0^1等于1，即a、b在这一位不同
> 
> 所以通过这一位，可以划分出两个区域
> 
> 一个区域是这一位为0的数 另一个区域是这一位为1的数
> 
> 所以可以通过其中任意一个区域找到a或者b
> 
> 即可以通过a^b^a得到另一个需要求的

相关知识/技巧

> 反码&原码=“快速得到仅保留原码最右边的1，其余位全部变0的码”
> 
> （0除外，本题无0，不讨论）
> 
> 举例：
> 
> （0101001001）原
> 
> &（1010110111）反
> 
> 得 （0000000001）

### 实现代码 ###

int eor = 0, rightOne;
            int[] arr = {2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 1, 9};
            for (int i : arr)
                eor ^= i;               //此时得到a^b
            rightOne = (~eor + 1) & eor;//保留eor的原码中最右侧的1，其余位变成0的码。
                                        //通过这个1，在数组中区分开a、b所在的部分
    
            int onlyOne = 0;            //等下把a或b其中的一个存放到这里
            for (int i : arr) {
                if ((i & rightOne) == 0) {
                    onlyOne ^= i;
                }
            }
    
            eor = eor ^ onlyOne;   //从a^b中取出一个
            System.out.println(onlyOne);
            System.out.println(eor);