数据结构

异或运算规则及其应用详解

异或运算简介

异或运算一般指异或。英文为exclusiveOR,缩写成xor。异或(xor)是一个数学运算符。它应用于逻辑运算。异或的数学符号为“⊕”,计算机符号为“xor”。其运算法则为:

a⊕b=(¬a∧b)∨(a∧¬b)

如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0。

异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1表示真,0表示假,则异或的运算法则为:0⊕0=0,1⊕0=1,0⊕1=1,1⊕1=0(同为0,异为1),这些法则与加法是相同的,只是不带进位。

异或略称为XOR、EOR、EX-OR

程序中有三种演算子:XOR、xor、⊕。

使用方法如下

z=x⊕y

z=xxory

异或运算规则

1.a⊕a=0

2.a⊕b=b⊕a

3.a⊕b⊕c=a⊕(b⊕c)=(a⊕b)⊕c;

4.d=a⊕b⊕c可以推出a=d⊕b⊕c.

5.a⊕b⊕a=b.

6.若x是二进制数0101,y是二进制数1011;

则x⊕y=1110

只有在两个比较的位不同时其结果是1,否则结果为0

即“两个输入相同时为0,不同则为1”!

异或运算规则及其应用

异或运算的作用

在计算机中普遍运用,异或(xor)的逻辑符号一般用xor,也有用⊕的:

真⊕假=真

假⊕真=真

假⊕假=假

真⊕真=假

或者为:

True⊕False=True

False⊕True=True

False⊕False=False

True⊕True=False

部分计算机语言用1表示真,用0表示假,所以两个字节按位异或如下

异或运算规则及其应用

下面是两个二进制数值进行异或计算:

异或运算规则及其应用

现实中用的都是十进制的数值,那么我们来看一看两个十进制数值是怎么进行异或计算:

5⊕3=?

1.进行异或计算前会把数值都转换为二进制:

5和3转为二进制分别为:0101、0011

异或运算规则及其应用

2.再把结果0110转换为十进制的:6

3.所以5⊕3=6

异或运算的巧用

与其它语言不同,C语言和C++语言的异或不用xor,而是用“^”,键入方式为Shift+6。(而其它语言的“^”一般表示乘方)

若需要交换两个变量的值,除了通常使用的借用中间变量进行交换外,还可以利用异或,仅使用两个变量进行交换,如:

异或运算规则及其应用

这样就完成了a与b的交换。

综上:同一变量与另一变量和其异或值异或等于另一个数,如(a^b)^a=b。

用例:可使用于加密算法某一环节或更多环节,使算法更复杂,不易被破解,安全性更高。

异或运算经典应用

参与运算的两个值,如果两个相应bit位相同,则结果为0,否则为1。

即:

0^0=0,

1^0=1,

0^1=1,

1^1=0

例如:10100001^00010001=10110000

按位异或的3个特点:

(1)0^0=0,0^1=10异或任何数=任何数

(2)1^0=1,1^1=01异或任何数-任何数取反

(3)任何数异或自己=把自己置0

按位异或的几个常见用途:

(1)使某些特定的位翻转

例如对数10100001的第2位和第3位翻转,则可以将该数与00000110进行按位异或运算。

10100001^00000110=10100111

(2)实现两个值的交换,而不必使用临时变量。

例如交换两个整数a=10100001,b=00000110的值,可通过下列语句实现:

a=a^b;//a=10100111

b=b^a;//b=10100001

a=a^b;//a=00000110

////////////////////////////////////////////////////////////

两个变量交换值的方法【http://blog.sina.com.cn/s/blog_676015470100izpg.html】

第一种方法,大家会借助第三个变量来实现:

如:C=A;A=B;B=C;

这种方法需要借助第三变量来实现;

第二种方法是利用加减法实现两个变量的交换,

如:A=A+B;B=A-B;A=A-B;

第三种方法是得用位异或运算来实现,也是效率最高的一种,在大量数据交换的时候,效率明显优于前两种方法,

如:A=A^B;B=A^B;A=A^B;

原理:利用一个数异或本身等于0和异或运算符合交换率。

PS:还有一篇更为深刻的文章对换值进行了探讨,作者的研究精神值得学习:

http://rednaxelafx.javaeye.com/blog/134002

/////////////////////////////////////////////////////////////

(3)在汇编语言中经常用于将变量置零:

xora,a

(4)快速判断两个值是否相等

举例1:判断两个整数a,b是否相等,则可通过下列语句实现:

return((a^b)==0)

举例2:Linux中最初的ipv6_addr_equal()函数的实现如下:

staticinlineintipv6_addr_equal(conststructin6_addr*a1,conststructin6_addr*a2)

{

return(a1-》s6_addr32[0]==a2-》s6_addr32[0]&&

a1-》s6_addr32[1]==a2-》s6_addr32[1]&&

a1-》s6_addr32[2]==a2-》s6_addr32[2]&&

a1-》s6_addr32[3]==a2-》s6_addr32[3]);

}

可以利用按位异或实现快速比较,最新的实现已经修改为:

staticinlineintipv6_addr_equal(conststructin6_addr*a1,conststructin6_addr*a2)

{

return(((a1-》s6_addr32[0]^a2-》s6_addr32[0])|

(a1-》s6_addr32[1]^a2-》s6_addr32[1])|

(a1-》s6_addr32[2]^a2-》s6_addr32[2])|

(a1-》s6_addr32[3]^a2-》s6_addr32[3]))==0);

}

转自:https://www.elecfans.com/d/641592.html