XOR — 神奇的按位运算符

原创 semlinker 全栈修仙之路 今天

一、异或运算符

在数字逻辑中，逻辑算符异或（ exclusiveor）是对两个运算元的一种逻辑分析类型，符号为 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 ⊕ 1 = 0
  2. 1 ⊕ 0 = 1
  3. 0 ⊕ 1 = 1
  4. 0 ⊕ 0 = 0

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

  1. 8 ^ 6 = 14
  2. 0000 1000
  3. ^ 0000 0110
  4. ------------
  5. 0000 1110

    二、异或运算符性质

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

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

p ⊕ q

  1. 0000 1111 //p=15
  2. ⊕ 0000 1000 //q=8
  3. ------------
  4. 0000 0111

q ⊕ p

  1. 0000 1000 // q=8
  2. ⊕ 0000 1111 // p=15
  3. ------------

  4. 0000 0111

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

    p ⊕ (q ⊕ r)

  5. 0000 1000 //q=8

  6. ⊕ 0000 0110 //r=6
  7. ------------
  8. 0000 1110 //(q ⊕ r)的结果
  9. ⊕ 0000 1111 //p=15
  10. ------------
  11. 0000 0001 // p ⊕ (q ⊕ r)的结果

(p ⊕ q) ⊕ r

  1. 0000 1111 //p=15
  2. ⊕ 0000 1000 //q=8
  3. ------------
  4. 0000 0111 //(p ⊕ q)的结果
  5. ⊕ 0000 0110 //r=6
  6. ------------

  7. 0000 0001 // (p ⊕ q) ⊕ r的结果

    2.3 恒等律：p ⊕ 0 = p

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

  8. 0000 1111 //p=15

  9. ⊕ 0000 0000
  10. ------------

  11. 0000 1111

    2.4 归零律：p ⊕ p = 0

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

  12. 0000 1111 //p=15

  13. ⊕ 0000 1111 //p=15
  14. ------------
  15. 0000 0000

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

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

p ⊕ q ⊕ q

  1. 0000 1111 //p=15
  2. ⊕ 0000 1000 //q=8
  3. ------------
  4. 0000 0111 //p ⊕ q的结果
  5. ⊕ 0000 1000 //q=8
  6. ------------

  7. 0000 1111 // p ⊕ q ⊕ q的结果

    三、异或运算符应用

    3.1 使某些特定的位翻转

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

  8. 0000 1010 //a=10

  9. ⊕ 0000 1100 //b=12
  10. ------------
  11. 0000 0110 //a ⊕ b的结果

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

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

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

  1. a = a ^ b; // ① a = a0 ^ b0，b = b0
  2. b = a ^ b; // ② a = a0 ^ b0，b = a0 ^ b0 ^ b0 = a0
  3. 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：

  1. function swap(a, b) {
  2. a = a ^ b;
  3. b = a ^ b;
  4. a = a ^ b;

  5. }

    3.3 只出现一次的数字

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

  6. A ^ C ^ B ^ C ^ B ^ A ^ D

  7. = A ^ A ^ B ^ B ^ C ^ C ^ D
  8. = 0 ^ 0 ^ 0 ^ D
  9. = 0 ^ D
  10. = D

JavaScript Code：

  1. function singleNumber(nums) {
  2. let ans = 0;
  3. for(const num of nums) {
  4. ans ^= num;
  5. }
  6. return ans;
  7. }

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

    给定两个整数 A 和 B，请计算把整数 A 转换为整数 B 所需翻转的位数。下面我们来举例说明一下：
名称 十进制 二进制
A 15 0000 1111
B 10 0000 1010

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

  1. 1 ⊕ 1 = 0
  2. 1 ⊕ 0 = 1
  3. 0 ⊕ 1 = 1
  4. 0 ⊕ 0 = 0

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

  1. 0000 1111
  2. ⊕ 0000 1010
  3. ------------
  4. 0000 0101

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

  1. function bitflip(a, b){
  2. let count = 0;
  3. let c = a ^ b;
  4. while(c != 0){
  5. c = c & (c - 1);
  6. count++;
  7. }
  8. return count;

  9. }

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

    给定一个二进制数如 01101100，求该二进制数中 1 的数量是奇数还是偶数。利用异或运算 p ⊕ 0 = p 恒等律的特性，上述问题可以这样解答： 0^1^1^0^1^1^0^0=0。若二进制数中每 1 位执行异或运算的结果为 1，则 1 的数量是奇数，而结果为 0，则 1 的数量是偶数。
    该功能的实际应用场景是奇偶校验，比如在串口通信中，每个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位判断接收到的数据是否有误。

    3.6 比特序列加密

    现代的密码都是建立在计算机的基础上，这是因为现代的密码所处理的数据量非常大，而且密码算法也非常复杂，不借助计算机的力量就无法完成加密和解密的操作。
    计算机的操作对象并不是文字，而是由 0 和 1 排列而成的比特序列。无论是文字、图片、声音、视频还是程序，在计算机中都是用比特序列来表示的。执行加密操作的程序，就是将表示明文的比特序列转换为表示密文的比特序列。
    这里我们来看一个比特序列异或运算的示例：

  10. 0 1 0 0 1 1 0 0 // A

  11. ⊕ 1 0 1 0 1 0 1 0 // B
  12. --------------------
  13. 1 1 1 0 0 1 1 0 //（A ⊕ B）的结果
  14. ⊕ 1 0 1 0 1 0 1 0 // B
  15. --------------------
  16. 0 1 0 0 1 1 0 0 // A

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

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

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

四、参考资源

  • 维基百科 - 逻辑异或

1. XOR — 神奇的按位运算符 - 图1

微信扫一扫
关注该公众号
1. XOR — 神奇的按位运算符 - 图2
全栈修仙之路FerRoad聚焦全栈，专注分享 Angular、TypeScript、Node.js/Java 、Spring 技术栈等全栈干货。
image.png
月发文数暂无

平均阅读数暂无
下载账号文章数据

  • 采集文章
  • 采集样式
  • 搜公众号
  • 查看封面
  • 生成长图
  • 近似文章

新榜合成器
0

添加到新榜合成器
×
拖拽到此处
图片将完成下载