欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

异或的性质及应用

程序员文章站 2022-07-15 12:06:10
...

亦或运算的概念

异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。

简单理解就是不进位加法,如1+1=0,0+0=0,1+0=1。

亦或运算的基本性质

1、交换律: a^b = b^a

2、结合律: a^b^c = a^(b^c)

3、对于任何数x,都有: x^x=0,x^0=x

4、自反性: a^b^b = a^0 = a

应用一:交换两个元素的值

通过按位异或运算,可以实现两个值的交换,而不必使用临时变量。例如交换两个整数a,b的值,可通过下列语句实现:

   int a=2,b=3      //a=0010,b=0111
   a=a^b;        //a=1101
   b=b^a;        //b=0010
   a=a^b;         //a=0111

应用二:找出多余的一个元素

1-1000放在含有1001个元素的数组中,只有唯一的一个元素值重复,其它均只出现
一次。每个数组元素只能访问一次,设计一个算法,将它找出来;不用辅助存储空
间,能否设计一个算法实现?

将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。时间复杂度为O(n)。

说明:
首先是异或运算满足交换律、结合律。
所以,1^2^...^n^...^n^...^1000,无论这两个n出现在什么位置,都可以转换成为1^2^...^1000^(n^n)的形式。

其次,对于任何数x,都有x^x=0,x^0=x。
所以1^2^...^n^...^n^...^1000 = 1^2^...^1000^(n^n)= 1^2^...^1000^0 = 1^2^...^1000(即序列中除了n的所有数的异或)。

令1^2^...^1000(序列中不包含n)的结果为T
则1^2^...^1000(序列中包含n)的结果就是T^n
因此T^(T^n)=n。
所以,将所有的数全部异或,得到的结果与1^2^3^...^1000的结果进行异或,得到的结果就是重复数。

相关标签: 异或