在 Java 基础中,我们最容易忽视的就是位运算符,而在位运算符中最容易忽视的就是异或运算符。今天遇到一道算法题就吃了亏,所以打算利用这道算法题学习一下异或运算符。


1. 算法题

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

说明:

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

示例 1:

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

示例 2:

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

这就是我遇到的一道算法题,有兴趣可以先做一做再往下看。


2. 异或运算符概述

异或运算符是对二进制的运算符。参与运算的两个值,如果两个相应bit位相同,则结果为0,否则为1。

例子:

161 ^ 6 = 167
相当于:
10100001 ^ 00000110 = 10100111

132 ^ 20 = 144
相当于:
10000100 ^ 00010100 = 10010000

看起来好像没什么用,但是异或运算有三个很重要的规律:

// 1.如果我们对 0 和二进制位做 XOR(异或) 运算,得到的仍然是这个二进制位
a ^ 0 = a
// 2.如果我们对相同的二进制位做 XOR 运算,返回的结果是 0
a ^ a = 0
// 3.XOR 运算满足交换律和结合律
a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

3. 排序法解题

上面的算法题有多种解法,区别在于性能的优劣。在这里我就讲两种解法,排序法和异或运算法。

为什么要讲排序法呢,因为这是我的第一个答案,也是比较容易的解法(除了穷举法,性能太低基本不考虑):

public static int singleNumber(int[] nums) {
Arrays.sort(nums);
int length=nums.length;
for(int i=0; i<length-1; i += 2){
if(nums[i] != nums[i+1]) return nums[i];
}
return nums[length-1];
}

通过16个测试用例:

语言 执行用时 内存消耗
Java 4 ms 42.3 MB

4. 异或运算法解题

根据题目描述 “除了某个元素只出现一次以外,其余每个元素均出现两次。” 结合异或运算的规律,我们只需要将所有的数进行 XOR 操作,得到那个唯一的数字。

例子:

参数:[4, 1, 2, 1, 2]
4 ^ 1 ^ 2 ^ 1 ^ 2 = (1 ^ 1) ^ (2 ^ 2) ^ 4 = 0 ^ 4 = 4
public int singleNumber(int[] nums) {
int length = nums.length;
int result = 0;
for(int i=0; i<length; i++){
result ^= nums[i];
}
return result;
}

通过16个测试用例:

语言 执行用时 内存消耗
Java 1 ms 42 MB

相比排序法要快了整整 3 ms,如果要处理巨大的数据量位运算就凸显了十分明显的优势。

评论