异或小知识

文章发布时间:

最后更新时间:

文章总字数:
2.1k

预计阅读时间:
8 分钟

页面浏览: 加载中...

阅读提示：本人没有良好的学术素养，因此在书写本文时，并没有注意用词的严谨性，文章为了易于理解，所举的例子也较为通俗，阅读时若不当的用词引起了您的红温，请原谅我。

定义与性质

这个部分包括对异或运算的规则和部分性质的介绍，若您对异或已经有了一部分的了解，可以直接跳过这个部分。

定义

异或是一种运算，一般作用于两个整数之间，更具体来说，作用于两个二进制整数之间。我们使用 符号来表示异或运算。

异或的运算规则为：二数相同为0，二数不同为1。如果难以理解的话，可以直接看下面的这个表格：

表达式 值
0
1
1
0

如果我们忽略进位信息，可以发现异或的运算结果和二进制下的加法的运算结果是相同的。因此也可以把异或理解为不进位的加法。

对于多位的数，异或运算应逐位异或，如：

基本性质

异或符合以下的运算法则：

  • 交换律：
  • 结合律：
  • 存在单位元 0：
  • 存在逆元且任何元素的逆元都是自己：

引申性质

异或的存储状态性质

异或是唯二的存在逆运算的位运算（另一个是非），对于一个有限位的存储单元来说，对其作与、或、左移、右移都可能会导致其数据无法通过逆运算还原。因此我们可以认为异或拥有存储状态的性质，也就是说，对于一个存储了的单元来说，它会隐含的存储 和 ，我们一定可以通过异或运算将其还原成 或是 。

  • 证明如下：
  • 证明如下：
  • 以上两条性质可以推广到位的情况。如：。实用意义可以参考异或加密。

异或的实用意义

交换两个数

在多数编程语言中，异或使用^运算符表示，这一节的代码为伪代码，您可以认为是C语言/C++/Java等语言。

一般地，想要交换两个数，我们可以这样写：

1
2
3
4
5
void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = tmep;
}

在知道了异或可以存储状态的特性后，我们也可以这样交换两个数：

1
2
3
4
5
void swap(int &a, int &b) {
    a ^= b; // a: a ^ b
    b ^= a; // b: b ^ (a ^ b) = a
    a ^= b; // a: (a ^ b) ^ a = b
}

前缀异或

问题描述：
输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l,r。
对于每次询问，输出原序列中从第l个数到第r个数的异或结果。

暴力的解决方案如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(vector<int>& nums, int n, int m) {
    // 为了方便理解，nums数组的下标为1到n，而不是0到n-1
    while (m -- ) {
        int l, r, result = 0;
        cin >> l >> r;

        for (int i = l; i <= r; i ++ ) {
            result ^= nums[i];
        }

        cout << result << '\n';
    }
}

考虑最坏的情况下，每次询问的长度最大为，因此运算的代码最多会被执行次。

让我们联想一下前缀和，如果您不了解前缀和，可以快速地过一下下面的介绍。

若要求给定的数列中，的值为多少，我们可以定义为，就会有

证明？自己证一下吧，总而言之，我们把称为数列的前缀和。

简短的证明思路

因为加法满足交换律和结合律，我们可以通过移项的方式，将部分元素消除。

与前缀和类似的是，异或运算也满足交换律和结合律，并且异或就是其本身的逆运算。因此我们定义一个数列为原序列的前个数相异或的结果，我们把这样的数列称为前缀异或，那么原序列中从第l个数到第r个数的异或结果便可以表示为，因此我们可以这样优化代码：

简短的证明思路

通过移项的方式，将部分元素消除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve(vector<int>& nums, int n, int m) {
    // 为了方便理解，nums数组的下标为1到n，而不是0到n-1

    nums[0] = 0;
    for (int i = 1; i <= n; i ++ ) {
        nums[i] ^= nums[i - 1];
    }

    while (m -- ) {
        int l, r；
        cin >> l >> r;
        cout << (nums[l - 1] ^ nums[r]) << '\n';
    }
}

考虑最坏的情况下，每次询问的长度最大为，因此运算的代码最多会被执行次。
当和的数量较大时，我们可以将二者都看作，因此第一种写法的复杂度约为，而第二种写法的复杂度约为，因此我们将二次级别的复杂度优化到了一次级别的复杂度。

异或加密

在计算机中，数据都是以二进制的 01 表示的，某些文件涉及到隐私安全，需要加密保护，异或的某些性质正好可以用来对加密/解密。

让我们假设某个文件中的某个字节的数据是这样的：10100011，我们设定一个密码，比如1010。

现在我们该如何对这个文件的安全进行保护呢？我们可以想到建立一个密码表(如下)，当用户输入一个密码后，软件从密码表中查找，如果密码正确，则允许用户正常地访问文件。

文件名 密码
test.txt 1010
hello.mp3 666

问题在于，如果黑客入侵了系统，那么黑客就可以直接找到文件的密码，此外，黑客还可以得知其他文件的密码。因此这样的系统安全性是非常低的。

所以我们不得不思考是否有其他的更安全的方案。我们注意到，异或满足的性质，因此我们可以让文件逐位地与密码相异或，这样就实现了对文件数据的加密。例如某个文件中的某个字节的数据是这样的：10100011，我们设定一个密码，比如1010，密码先与低位的0011进行异或运算，得到1001，再与高位的1010进行异或运算，得到0000，因此最后得到的加密后数据为00001001。对文件的所有字节的数据采用同样的运算后，整个文件的数据便成了加密后的密文。

当用户想打开这个文件时，用户首先输入密码，软件所做的操作是，将文件的二进制数据依次与密码进行异或运算，00001001在运算后便可以得到原始的10100011。这样做的好处在于：

  • 文件实现了真正意义上的加密，他人通过分享的方式取得了文件，文件依然是加密的状态。
  • 文件的密码没有存储在操作系统中，减少了被黑客入侵的风险。
  • 输入错误的密码会导致文件数据变成错误的数据，我们可以设立某个字段为关键字，用来校验密码是否正确，如某个字段加密前为'abc'，如果用户输入了错误的密码，导致这个字段变成了'1a8'，软件检测到校验位的字段内容不是'abc'，就可以得知用户输入的密码有误。
  • 基于这样的方案，我们还可以设计出二级加密、三级加密等。
≡