跳到主要内容

关于异或运算的一点随想

面试算法题警告

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 变量,来暂时存储将要被覆盖的数据。这样占用了额外的空间,既没有派上很大用场,又会导致后续的一系列在栈上做增减的工作(此处存疑),很不优雅;能不能不创造临时变量,直接在 ab 上做文章?来康康这个:

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

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

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=B3B2G1=B2B1G0=B1B0\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 中只提供了或门(两个输入端用红石线相连)和非门(红石火把);那么,任务就是把异或用或和非来表示。

AB=AB+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。

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