关于异或运算的一点随想
面试算法题警告
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)
第一种思路:暴力扫描法,需要 时间;第二种,填表记录法,需要 时间和 空间。那么,有没有 时间和 空间的优美算法?
这种算法对于熟悉异或思想的人,实际上并不难想到:
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 和那个孤单的数异或,结果便是那个数本身。
所以,只要看到“相同”“重复出现”等字样,就应当把思路往异或上去靠。
三、重回格雷码
格雷码的得出,除了比较繁琐的递归法外,还有一种异或法:
格雷码是为了杜绝进位时出现多个数位改变的情况;而在上面的算式中,如果两个数位(用 表示)同时从 11 变成 00,格雷码数位(用 表示)仍然保持为 0。
四、Minecraft 中的异或门
来讲讲如何在 Minecraft 中建造异或门。
Minecraft 中只提供了或门(两个输入端用红石线相连)和非门(红石火把);那么,任务就是把异或用或和非来表示。
至于为什么要写成最后的形式而不是倒数第二个式子,就需要一些逻辑设计的经验了。最后一种看似更繁琐,实际上独立项从四个变成了三个,便于电路设计。
接下来,运用丰富的红石电路设计经验,就搞出来了:
从左至右,分别对应输入是 00,01,11。这种设计,非常紧凑,但延时要比另一种也很常用的设计(虽然我个人不用)多 1 tick。
由此可见,异或运算的确是一种十分实用,潜力无限的工具。希望大家能使用好它。