Skip to main content

关于异或运算的一点随想

面试算法题警告

Minecraft教程警告

本文默认读者了解基本异或运算知识，如：0^0=0, 0^1=1, 1^1=0, x^0=x, x^1=x', x^x=0 等

一、从一类经典面试题类型讲起​

算法题中，经常会出现数组类的题目——刁钻的是，这种题目往往要求原地改变数组的值而不是返回新的数组。比如这道题——

给定一个 n × n 的二维矩阵表示一个图像。将图像顺时针旋转 90 度。

必须在原地旋转图像，直接修改输入的二维矩阵。

示例 1: 给定

matrix =
[[1,2,3],
 [4,5,6],
 [7,8,9]],

原地旋转输入矩阵，使其变为:

[[7,4,1],
 [8,5,2],
 [9,6,3]]

示例 2: 给定

matrix =
[[ 5, 1, 9,11],
 [ 2, 4, 8,10],
 [13, 3, 6, 7],
 [15,14,12,16]],

原地旋转输入矩阵，使其变为:

[[15,13, 2, 5],
 [14, 3, 4, 1],
 [12, 6, 8, 9],
 [16, 7,10,11]]

来源：力扣（LeetCode）

链接：48. 旋转图像 - 力扣（LeetCode）

题目本身不难，但绝大多数算法时间都是 1ms（java 数据），精益求精的程序猿肯定会想尽办法再从这里面抠出 1ms 来；那么，不改变算法的情况下，有哪些细节可以优化呢？在原地改变数组的算法中，几乎一定会涉及两数的交换；如果要写出一个 swap(int a, int b) 函数，绝大多数人写出来应该类似这样：

public void swap(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

创建了一个临时 temp 变量，来暂时存储将要被覆盖的数据。这样占用了额外的空间，既没有派上很大用场，又会导致后续的一系列在栈上做增减的工作（此处存疑），很不优雅；能不能不创造临时变量，直接在 a 和 b 上做文章？来康康这个：

//请注意添加对此类算法的注释以免变成无人理解的垃圾代码
public void swap(int a, int b) {
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;
}

有没有立即觉得优雅简洁了？三个赋值语句，右边都是 a^b，左边则分别是 a、b、a——它是怎么实现的？一步步看：

a = a ^ b
b = a ^ b = (a ^ b) ^ b //代入a的表达式
          = a ^ (b ^ b) //结合律
          = a ^ 0       //变量与自身异或，结果为0
          = a           //成功交换
a = a ^ b = (a ^ b) ^ a //代入原本a与b的值
          = (a ^ a) ^ b //结合律+交换律
          = 0 ^ b       //变量与自身异或，结果为0
          = b           //成功交换

由于一般的编译器不可能发现并优化成这种方法，因此需要程序员本人了解它并使用。而且，这样的算法，性能果然得到了一定提升，从 1ms 变成 0ms，成功碾压 100%的 java 程序，的确是异常神奇呢……

二、再接再厉​

看一道更加经典的题目：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/single-number

第一种思路：暴力扫描法，需要 O(n2)\mathcal{O}(n^2) 时间；第二种，填表记录法，需要 O(n)\mathcal{O}(n) 时间和 O(n)\mathcal{O}(n) 空间。那么，有没有 O(n)\mathcal{O}(n) 时间和 O(1)\mathcal{O}(1) 空间的优美算法？

这种算法对于熟悉异或思想的人，实际上并不难想到：

public int singleNumber(int[] nums) {
    int a = 0;
    for (int i = 0; i < nums.length; i++) {
        a ^= nums[i];
    }
    return a;
}

因为把整个数组全部按位异或后，相同的数都两两抵消，变成 0 了，一堆 0 在一起运算，仍然是 0；0 和那个孤单的数异或，结果便是那个数本身。

所以，只要看到“相同”“重复出现”等字样，就应当把思路往异或上去靠。

三、重回格雷码​

格雷码的得出，除了比较繁琐的递归法外，还有一种异或法：

G3=B3G2=B3⊕B2G1=B2⊕B1G0=B1⊕B0\begin{aligned} G_3&=B_3\\ G_2&=B_3\oplus B_2\\ G_1&=B_2\oplus B_1\\ G_0&=B_1\oplus B_0 \end{aligned}

格雷码是为了杜绝进位时出现多个数位改变的情况；而在上面的算式中，如果两个数位（用 BB 表示）同时从 11 变成 00，格雷码数位（用 GG 表示）仍然保持为 0。

四、Minecraft 中的异或门​

来讲讲如何在 Minecraft 中建造异或门。

Minecraft 中只提供了或门（两个输入端用红石线相连）和非门（红石火把）；那么，任务就是把异或用或和非来表示。

A⊕B=A′B+AB′=(A′+B)′+(A+B′)′=(A′+AB)′+(B′+AB)′\begin{aligned} A\oplus B=A'B+AB'=(A'+B)'+(A+B')'=(A'+AB)'+(B'+AB)' \end{aligned}

至于为什么要写成最后的形式而不是倒数第二个式子，就需要一些逻辑设计的经验了。最后一种看似更繁琐，实际上独立项从四个变成了三个，便于电路设计。

接下来，运用丰富的红石电路设计经验，就搞出来了：

从左至右，分别对应输入是 00，01，11。这种设计，非常紧凑，但延时要比另一种也很常用的设计（虽然我个人不用）多 1 tick。

由此可见，异或运算的确是一种十分实用，潜力无限的工具。希望大家能使用好它。