XOR — 神奇的按位运算符

戚建辉
• 阅读 14476

一、异或运算符

在数字逻辑中,逻辑算符异或(exclusive or)是对两个运算元的一种逻辑分析类型,符号为 XOR 或 ⊕(编程语言中常用 ^)。但与一般的逻辑或不同,异或算符的值为真仅当两个运算元中恰有一个的值为真,而另外一个的值为非真。

1.1 异或运算的表示形式

名称 符号
数学符号
英文简称 xor
程序符号 ^

1.2 异或运算的真值表

异或运算 p ⊕ q 的真值表如下:

p q
T T F
T F T
F T T
F F F

无论怎样改变同一行中 p,q 的位置,真值表都是成立的。

1.3 异或运算规则

由上述的真值表,我们可以总结出以下异或运算的运算规则:

1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

下面我们以 8 ^ 6 为例,来实际体验一下异或运算。

8 ^ 6 = 14
  0000 1000
^ 0000 0110
------------
  0000 1110

二、异或运算符性质

名称 二进制表达式(8位)
p 15 0000 1111
q 8 0000 1000
r 6 0000 0110

2.1 交换律:p ⊕ q = q ⊕ p

p ⊕ q

  0000 1111 //p=15
⊕ 0000 1000 //q=8
------------
  0000 0111

q ⊕ p

  0000 1000 // q=8
⊕ 0000 1111 // p=15
------------
  0000 0111

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

p ⊕ (q ⊕ r)

  0000 1000 //q=8
⊕ 0000 0110 //r=6
------------
  0000 1110 //(q ⊕ r)的结果
⊕ 0000 1111 //p=15
------------
  0000 0001 // p ⊕ (q ⊕ r)的结果

(p ⊕ q) ⊕ r

  0000 1111 //p=15
⊕ 0000 1000 //q=8
------------
  0000 0111 //(p ⊕ q)的结果
⊕ 0000 0110 //r=6
------------
  0000 0001 // (p ⊕ q) ⊕ r的结果

2.3 恒等律:p ⊕ 0 = p

一个数与 0 进行异或运算等于它本身

  0000 1111 //p=15
⊕ 0000 0000
------------
  0000 1111

2.4 归零律:p ⊕ p = 0

一个数与它本身进行异或运算等于 0

  0000 1111 //p=15
⊕ 0000 1111 //p=15
------------
  0000 0000

基于该特性,可以通过 a ⊕ b == 0 来判断两个整数的值是否相等。

2.5 自反:p ⊕ q ⊕ q = p ⊕ 0 = p

p ⊕ q ⊕ q

  0000 1111 //p=15
⊕ 0000 1000 //q=8
------------
  0000 0111 //p ⊕ q的结果
⊕ 0000 1000 //q=8
------------
  0000 1111 // p ⊕ q ⊕ q的结果

三、异或运算符应用

3.1 使某些特定的位翻转

给定整数 a,要求翻转 a 对应二进制表达式中的特定位。假设整数 a 的值为 10,其对应二进制表达式为 0000 1010(以 8 位为例),我们要求对第 3 位和第 4 位进行翻转,要实现这个需求,可以将 a 与 b(12) 进行按位异或运算。

  0000 1010 //a=10
⊕ 0000 1100 //b=12
------------
  0000 0110 //a ⊕ b的结果 

通过观察以上结果,我们可以发现第 3 位(0 -> 1)和第 4 位(1 -> 0)都完成了翻转。

3.2 不用额外变量交换两个整数的值

给定整数 a 和 b,不用额外变量交换两个整数的值。针对该问题,可以用以下三行代码来交换 a 和 b 的值(a0 与 b0 表示原始值):

a = a ^ b; // ① a = a0 ^ b0,b = b0
b = a ^ b; // ② a = a0 ^ b0,b = a0 ^ b0 ^ b0 = a0
a = a ^ b; // ③ a = a0 ^ b0 ^ a0 = b0,b = a0

下面我们来分析一下上述代码的执行过程:

  • 执行完第一行代码之后,a 的值变成 a0 ^ b0 的值,记为 c,而 b 的值保持不变;
  • 执行完第二行代码之后,a 的值不变仍为 c,而 b 的值为 c ^ b 即 a0 ^ b0 ^ b0 的运算结果,利用前面提到异或运算的特性可以得出 b = a0 ^ (b0 ^ b0) = a0 ^ 0 = a0,即 b = a0;
  • 执行完第三行代码之后,a 的值为 a0 ^ b0 ^ a0 的运算结果,同样利用异或运算的特性可以得出 a = b0 ^ (a0 ^ a0) = b0 ^ 0,即 a = b0。

JavaScript Code:

function swap(a, b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

3.3 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。异或运算符满足交换律和结合律,所以假设有一个非空整数数组为:[A C B C B A D],把每一项进行异或运算:

 A ^ C ^ B ^ C ^ B ^ A ^ D
 = A ^ A ^ B ^ B ^ C ^ C ^ D
 = 0 ^ 0 ^ 0 ^ D
 = 0 ^ D
 = D

JavaScript Code:

function singleNumber(nums) {
    let ans = 0;
    for(const num of nums) {
        ans ^= num;
    }
    return ans;
}

3.4 确定将整数 A 转换为整数 B 所需翻转的位数

给定两个整数 A 和 B,请计算把整数 A 转换为整数 B 所需翻转的位数。下面我们来举例说明一下:

名称 十进制 二进制
A 15 0000 1111
B 10 0000 1010

通过观察上述表格,要把整数 A(15)转换成整数 B(10),需要翻转的位数为 2。这里我们再来回顾一下异或的运算规则:

1 ⊕ 1 = 0
1 ⊕ 0 = 1
0 ⊕ 1 = 1
0 ⊕ 0 = 0

然后我们对整数 A 和整数 B 执行异或运算:

  0000 1111
⊕ 0000 1010
------------
  0000 0101

这时我们可以知道,如果整数 A 和整数 B 对应位的值不一致的话,当前位的异或结果就为 1,在转换过程中就需要进行翻转。而要计算整数 A 转换为整数 B 所需翻转的位数,就可以转换为计算 A ⊕ B 运算结果二进制数中 1 的个数。

JavaScript Code:

function bitflip(a, b){
   let count = 0;
   let c = a ^ b;
   while(c != 0){
      c = c & (c - 1);
      count++;  
   }
   return count;
}

3.5 判断一个二进制数中 1 的数量是奇数还是偶数

给定一个二进制数如 0110 1100,求该二进制数中 1 的数量是奇数还是偶数。利用异或运算 p ⊕ 0 = p 恒等律的特性,上述问题可以这样解答:0 ^ 1 ^ 1 ^ 0 ^ 1 ^ 1 ^ 0 ^ 0 = 0。若二进制数中每 1 位执行异或运算的结果为 1,则 1 的数量是奇数,而结果为 0,则 1 的数量是偶数。

该功能的实际应用场景是奇偶校验,比如在串口通信中,每个字节的数据都计算一个校验位,数据和校验位一起发送出去,这样接收方可以根据校验位判断接收到的数据是否有误。

3.6 比特序列加密

现代的密码都是建立在计算机的基础上,这是因为现代的密码所处理的数据量非常大,而且密码算法也非常复杂,不借助计算机的力量就无法完成加密和解密的操作。

计算机的操作对象并不是文字,而是由 0 和 1 排列而成的比特序列。无论是文字、图片、声音、视频还是程序,在计算机中都是用比特序列来表示的。执行加密操作的程序,就是将表示明文的比特序列转换为表示密文的比特序列。

这里我们来看一个比特序列异或运算的示例:

  0 1 0 0 1 1 0 0 // A
⊕ 1 0 1 0 1 0 1 0 // B 
--------------------
  1 1 1 0 0 1 1 0 //(A ⊕ B)的结果
⊕ 1 0 1 0 1 0 1 0 // B 
--------------------
  0 1 0 0 1 1 0 0 // A

可能你已经发现了,上面的计算过程和加密、解密的步骤非常相似。

  • 将明文 A 用密钥 B 进行加密,得到密文 A ⊕ B
  • 将密文 A ⊕ B 的结果异或密钥 B 进行解密,得到明文 A

实际上,只要选择一个合适的 B,仅仅使用 XOR 就可以实现一个高强度的密码。

四、参考资源

本人的全栈修仙之路订阅号,会定期分享 Angular、TypeScript、Node.js/Java 、Spring 相关文章,欢迎感兴趣的小伙伴订阅哈!

XOR — 神奇的按位运算符

点赞
收藏
评论区
推荐文章
Stella981 Stella981
3年前
ASMSupport教程4.8 生成逻辑运算操作
<p在java中有以下逻辑运算符:</p<ul<li&amp;&amp;:条件与</li<li||:条件或</li<li&amp;:布尔型的逻辑与</li<li|:布尔型的逻辑或</li<li^:布尔型的逻辑异或</li<li!:非操作</li</ul<p那么接下来我们将些段例子
Stella981 Stella981
3年前
Python运算符大全
  一、Python的算术运算  Python的算术运算符与C语言类似,略有不同。包括加()、减()、乘(\)、除(/)、取余(%)、按位或(|)、按位与(&)、按位求补(~)、左移位(<<)、右移位()、单目求反()、幂运算(\\)、整除运算(//)、增强运算、增强矩阵乘法(@)。  增强运算是将算术运算符或逻辑运算符放到等号的左
Wesley13 Wesley13
3年前
C语言位运算
位运算应用口诀清零取反要用与,某位置一可用或若要取反和交换,轻轻松松用异或移位运算要点1它们都是双目运算符,两个运算分量都是整形,结果也是整形。        2"<<"左移:右边空出的位上补0,左边的位将从字头挤掉,其值相当于乘2。       3""右移:右边的位被挤掉。对于左边移出的空位,如果是正数则空
Wesley13 Wesley13
3年前
C位运算中 异或运算符的 几点注意与示例
C语言的异或运算的运算原理应用。需要注意的是位运算是符合交换律,结合律及分配律的/AllRightsReserved20072015
Wesley13 Wesley13
3年前
C#位运算
在C中可以对整型运算对象按位进行逻辑运算,按位进行逻辑运算的意义是:依次取被运算对象的每个位,进行逻辑运算,每个位的逻辑运算结果是结果值的每个位,C支持的位逻辑运算符如下表。!(https://oscimg.oschina.net/oscnet/e3ff3ca0d8190d7cf6a5c8269feaab32004.jpg)1、位逻辑非运算
Wesley13 Wesley13
3年前
LUA教程表达式逻辑运算符
Lua中的逻辑操作符有and,or,以及not。 和控制结构一样,所有的逻辑操作符把false和nil都作为假,而其它的一切都当作真。andornot逻辑运算符认为false和nil是假(false),其他为真,0也是true.and和or的运算结果不是true和false,而是和它的两个操
Stella981 Stella981
3年前
Lua 运算符
Lua运算符运算符是一个特殊的符号,用于告诉解释器执行特定的数学或逻辑运算。Lua提供了以下几种运算符类型:算术运算符关系运算符逻辑运算符其他运算符算术运算符下表列出了Lua语言中的常用算术运算符,设定A的值为10,B的值为20:操作符
Stella981 Stella981
3年前
JavaScript学习总结(二)——逻辑Not运算符详解
在JavaScript中,逻辑NOT运算符与C和Java中的逻辑NOT运算符相同,都由感叹号(!)表示。与逻辑OR和逻辑AND运算符不同的是,逻辑NOT运算符返回的一定是Boolean值。逻辑NOT运算符的行为如下:如果运算数是对象,返回false如果运算数是数字0,返回true如
小万哥 小万哥
1年前
C# 运算符详解:包含算术、赋值、比较、逻辑运算符及 Math 类应用
运算符用于对变量和值执行操作。在C中,有多种运算符可用,包括算术运算符、关系运算符、逻辑运算符等。算术运算符算术运算符用于执行常见的数学运算:csharpintx10050;//加法,结果为150intyx30;//减法,结果为120intzx2;//乘
小万哥 小万哥
1年前
Python 运算符
运算符用于对变量和值执行操作。在下面的示例中,我们使用运算符将两个值相加:pythonprint(105)Python将运算符分为以下几组:算术运算符赋值运算符比较运算符逻辑运算符身份运算符成员运算符位运算符算术运算符算术运算符用于对数字值执行常见的数
戚建辉
戚建辉
Lv1
只在此山中,云深不知处。
文章
3
粉丝
0
获赞
0