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