异或

更新时间:2024-09-18 19:34

异或(Exclusive OR,简称 XOR)是一种数学运算符,常用于逻辑运算与计算机中的位运算。当 仅当两个输入值不同时,异或运算输出为真(1),否则输出为假(0),即“同为 0,异为 1”。异或运算可以通过数学符号“⊕”表示, 具有交换律、结合律、恒等律等性质。

定义

异或是一个数学运算符,它应用于逻辑运算与计算机中的位运算。

令 p 和 q 为命题。p 和 q 的异或是这样一个命题:当p 和 q 中恰好只有一个为真时命题为真,否则为假。

p 异或 q 通常记作 p XOR q 或 p⊕ q。在编程语言中通常为 p^q。

如 p、q 两个值不相同,则异或结果为 1。如果 p、q 两个值相同,异或结果为 0,即异或的运算法则为:0 ⊕ 0 = 0,1 ⊕ 0 = 1,0 ⊕ 1 = 1,1 ⊕ 1 = 0(同为 0,异为 1)。这种运算捕捉了输入位的“排他性”,即输入不能同时为真。

异或也叫半加运算,其运算法则相当于不带进位的二进制加法:二进制下用1 表示真,0 表示假,这些法则与加法是相同的,只是不带进位,所以异或常被认作不进位加法。

真值表

异或运算的真值表如下:

运算示例

例如计算 5 ⊕ 3, 需要先转换成二进制。5 = 1012 ,3 = 0112

即先转换为二进制,再对每一位取异或,输出二进制后再转换为十进制。

5 ⊕ 3 = 6。

公式

在数学和工程学中,常常用其他的逻辑运算符来表示异或算符。异或算符可以使用逻辑算符逻辑与∧,逻辑或 ∨ 和逻辑非 ¬ 表示为:

(异或的析取范式)

(异或的合取范式)

公式可由真值表得出,或用摩根定律等逻辑运算公式相互推得。

性质

交换律:p ⊕ q = q ⊕ p

结合律:p ⊕ (q ⊕ r) = (p ⊕ q) ⊕ r

恒等律:p ⊕ 0 = p

归零律:p ⊕ p = 0

对合运算:p ⊕ q ⊕ q = p ⊕ 0 = p

逆元:对于任何布尔值a, 有 a ⊕ 0 = a 与 a ⊕ a = 0, 即对于异或操作,每一个布尔值 a 的逆元就是它本身。

由以上性质可得,若 A ⊕ B = C ,则 A ⊕ C = B 且B ⊕ C = A。可以用这条性质进行简单的数据交换。

与现代代数的联系

虽然逻辑系统中的运算符 ∧(合取)和 ∨(析取)非常有用,但它们在以下方面缺乏更具一般性的结构:

系统 ({T,F }, ∧) 和 ({T,F }, ∨) 都是单调的,但都不是群。这不幸地阻止了将这两个系统组合成更大的结构,如数学环。

然而,使用异或的系统 ({T,F }, ⊕) 是阿贝尔群。运算符 ∧ 和 ⊕ 在元素 {T,F } 上的组合产生了众所周知的两元素域 F2。这个域可以表示任何逻辑系统的逻辑,并且具有域的代数分析工具的优势。

更具体地说,如果将 F 与0 关联,将T 与 1 关联,那么可以将逻辑”AND” 操作解释为F2 上的乘法,将”XOR” 操作解释为F2 上的加法:

使用这个基础,将布尔函数描述为 F2 中的多项式,被称为函数的代数标准型。

异或运算与兼或运算的区别

异或运算具有排他性,即强调“互斥”关系,表示两个事件不能同时为真;而兼或(逻辑或)强调“包含”关系,表示只要至少有一个事件为真,整体结果就为真。

例如,命题“数学或英语成绩在90分以上者,可以获得奖励。” 这体现了兼或的逻辑:至少一个条件(数学或英语成绩在90分以上)满足,就能得到奖励。若两个条件都满足,也能获得奖励。

在选择晚餐套餐时,命题“选择晚餐套餐:你可以选择意大利面或寿司。” 这是一个典型的异或场景:要么选择意大利面,要么选择寿司,但不能两者同时选择。

应用

奇偶校验

异或门常用于实现奇偶校验,这是一种简单的错误检测方法。在串行数据传输中,为了确保数据的正确性,我们通常会在数据位之后添加一个奇偶校验位。这个校验位的值是通过对所有数据位进行异或运算得到的,它的作用是使得整个数据字(包括数据位和校验位)中的“1”的个数总是奇数(奇校验)或者偶数(偶校验)。

加法器设计

在数字电路中,异或门是实现全加器的关键元素。全加器是用于实现二进制数加法的电路,它接收两个输入位和一个进位位,然后输出一个和位和一个新的进位位。其中的和位就是通过异或门实现的,因为异或运算的结果与二进制加法的结果相同(忽略进位)。

密码学

在一些流密码中,明文会与一个密钥流进行异或运算,生成密文。由于异或运算的逆运算就是它自己,所以在解密时,只需要将密文与同样的密钥流进行异或运算,就可以得到原始的明文。实际在密码学中还有其他广泛的应用,例如循环差分异或密码、量子图像加密算法等。

过滤冗余信息

计算机中可以通过异或算法去除多张图片中相同的信息,从而发现一些信息增量。

在天文学中,异或运算也被用于处理图像数据。天文学家可以通过对连续的天文图像进行异或运算,去除静态的背景信息,从而更容易地识别出正在移动的星体。这种方法可以有效地过滤掉冗余的信息,使得研究者可以更专注于他们感兴趣的目标。

高级算法设计

异或也被用于一些高级的算法设计,如哈希函数、伪随机数生成、数据压缩和图论中的最小生成树算法等。通过这些广泛的应用,异或成为了现代信息处理和安全保障领域中不可或缺的工具。

数据交换

异或运算还可以用于在不引入临时变量的情况下交换两个变量的值。这是因为异或运算满足交换律和结合律,而且任何值与自身进行异或运算的结果都是 0,任何值与 0 进行异或运算的结果都是它自己。

代码实现

使用异或运算进行数据交换的简单代码实现:

Java

Python

C/C++

意义

异或运算作为一种基础的逻辑操作,不仅在数字电路设计中具有广泛应用,而 在现代信息技术的发展过程中扮演了重要角色。其简单却强大的特性,使其成为了数据处理、加密技术以及信息交换等多个领域的核心工具。无论是在保障数据传输的可靠性,还是提升计算效率、推动密码学研究,异或运算的应用都展现了其对科技进步和人类发展不可或缺的贡献。

免责声明
隐私政策
用户协议
目录 22
0{{catalogNumber[index]}}. {{item.title}}
{{item.title}}