二进制运算中,异或无处不在。由于其各种不错的性质在计算机中应用很广。由于日常中很少接触到需要应用到异或的算法,对异或的印象也只停留在各种计算机底层设计中,终归是纸上谈兵。最近接触到了一个使用异或的巧妙算法,便发现自己对异或的理解过于肤浅。
异或简介
- 交换律
- 结合律
- $x;XOR;0 = x$ | $x;XOR;x = 0$
- $A;XOR;\underline{B;XOR;B} = A;XOR;\underline{0} = A $
使用异或的如上性质,在交换两个变量的值时,可以直接通过异或实现而不用使用额外空间:
A = A ^ B;
B = B ^ A;//B = B ^ A ^ B = B ^ B ^ A = A
A = A ^ B;//A = A ^ B ^ A = B
引子
**问题:**在一个数组中,如果只有一个数重复出现了奇数次而其余数出现了偶数次,设计一个算法来找出这个出现奇数次的数。要求算法满足时间复杂度$O(n)$,空间复杂度$O(1)$。
传统解法
按照传统的思路来的话,可以使用一个HashSet
,每次读入一个数据,如果在HashSet
中则去掉这个数,反之则将该数字加入HashSet
。而这个问题要求$O(1)$的空间复杂度,只能另辟蹊径。
异或解法
可以注意到,这个问题如果使用异或的思想来解决的话便很方便。
假设原数组 nums = {1, 2, 2, 3, 3, 4, 4}
所求数字便为 1。初始化 Mask = 0,对每个元素都进行运算Mask ^= num[i]
。运算后得Mask = 1
。即得到了所求的数字。
应用
**问题:**一个整型数组 nums
里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是$O(n)$,空间复杂度是$O(1)$。
传统解法
使用HashSet
来实现:
class Solution {
public int[] singleNumbers(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int n : nums) {
if (set.contains(n))
set.remove(n);
else
set.add(n);
}
int index = 0;
int[] res = new int[set.size()];
for(int i : set){
res[index++] = i;
}
return res;
}
}
异或解法
思路:首先利用异或的性质,将数组内所有元素连续异或一次,得到两个只出现一次的元素的异或值。如:nums = {1, 2, 3, 3, 4, 5, 5}
连续异或后得到1 ^ 2
的值。接下来需要利用异或后的值来分离二者,注意到可以通过二者异或得到的掩码二进制最低位的 1 来分成两组,将问题转换为了引子中所提到的问题,再分别对每组进行连续异或便得到了所求的两个元素。
class Solution {
public int[] singleNumbers(int[] nums) {
int mask = 0;
//得到掩码
for(int num : nums){
mask ^= num;
}
//得到分组的依据:掩码二进制最右边的 1
int flag = (-mask) & mask;
int elem1 = 0;
int elem2 = 0;
//分成两个组进行异或,每组异或后的结果就是不相同两个数的其中之一
for(int num : nums){
if((flag & num) == 0){
elem1 ^= num;
}
else{
elem2 ^= num;
}
}
return new int[]{elem1, elem2};
}
}
最后
利用异或可以实现很多精妙的算法,但是其还是有局限性,且写出的代码往往难以理解,可读性较差,如果代码文档或注释不完整的话很容易让其他人感到迷惑,在日常开发中还是HashSet
来的实在。个人认为,一个算法的好坏不应只关注其性能如何如何快,还应注意其可读性如何,以及是否方便维护、线程是否安全等其他方面。