异或运算的概念
- 对应二进制位进行异或运算
- 对应二进制位上，相同结果为0，不同结果为1
小技巧：异或运算可以记为无进位相加
现在有两个整数 A A A和 B B B， A A A 等于7 ， B B B等于13，那么 A A A^ B B B怎么运算呢？
// 十进制 A = 7 B = 13
// 二级制：
// A: 0111
// B: 1101
// --------
// 1010
A A A ^ B = ( 1010 ) 2 = ( 10 ) 10 B = (1010)_2 = (10)_{10} B=(1010)2=(10)10，
异或运算的性质
- 满足交换律
- A A A ^ B B B = B B B ^ A A A
- 证明: A A A和 B B B无进位相加等于 B B B和 A A A无进位相加
- 满足结合律
- ( A (A (A ^ B ) B) B) ^ C = C = C= A A A ^ ( B (B (B^ C ) C) C)
- 证明： A A A和 B B B无进位相加在和 C C C无进位相加等于 B B B和 C C C无进位相加在和 A A A无进位相加
- * 0 0 0 ^ N N N = N = N =N>
- 证明： 0 0 0和 N N N无进位相加结果还是 N N N
- N N N ^ N N N = 0 0 0
- 证明： N N N和 N N N无进位相加结果为 0 0 0
请理解并记住这里的性质，后面会使用到。
交换两个变量的值（不使用额外变量）
这是一个经典的面试题,代码如下，请读者先自行理解。
public class Test {
// 交换数组中 i 和 j 两个位置的值（注意i ！= j，如果i == j 那么 arr[i] == arr[j]）
// 那么经过异或运算（N ^ N = 0）后会把arr[i] arr[j]位置的值刷成0
public static void swap(int[] arr,int i,int j) {
arr[i] ^= arr[j];
arr[j] ^= arr[i];
arr[i] ^= arr[j];
}
public static void main(String[] args) {
int a = 3;
int b = 5;
// swap1
a = a ^ b; // ①
b = a ^ b; // ②
a = a ^ b; // ③
System.out.println(a + " " + b);
}
}
为什么跑完①②③就能完成两个变量的交换呢？现在我们将 a a a记作 a 1 a_1 a1,b记作 b 1 b_1 b1，第一步， a = a 1 a = a_1 a=a1 ^ b 1 b_1 b1，第二部， b = ( a 1 b = (a_1 b=(a1 ^ b 1 ) b_1) b1) ^ b 1 = a 1 = a b_1 = a_1 = a b1=a1=a，第三步， a = ( a 1 a = (a_1 a=(a1 ^ b 1 ) b_1) b1)^ a 1 = b 1 a_1 = b_1 a1=b1，在这里进行计算式不要忽视了上一步计算的对 a b a b ab的影响。这样跑完这三行代码之后就玩成了对两个变量的交换。注意：位运算的效率远高于算术运算。
只出现一次的数字
这是一道leetcode原题，传送门请点我!!!
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
那么怎么考虑这个问题呢？我们前面讲过异或运算满足交换律和结合律那么在这里设这组数为：
n u m s 1 , n u m s 2 , n u m s 3 , . . . . . . n u m s n − 1 nums_1,nums_2,nums_3,...... nums_{n - 1} nums1,nums2,nums3,......numsn−1，
假设 n u m s i nums_i numsi 为数组中出现了奇数次的数，我们队这组数调整顺序：
n u m s i , n u m s 1 , n u m s 2 , . . . . . . n u m s i , n u m s i + 1 , . . . . . . n u m s n − 1 nums_i, nums_1 , nums_2, ...... nums_{i}, nums_{i + 1},......nums_{n-1} numsi,nums1,nums2,......numsi,numsi+1,......numsn−1，
调整完顺序之后，由于除了 n u m s i nums_i numsi其他数都出现了偶数次那么有：
n u m s i nums_i numsi ^ n u m s 1 nums_1 nums1 ^ n u m s 2 nums_2 nums2 ^ … ^ n u m s n − 1 = n u m s i nums_{n - 1} = nums_i numsn−1=numsi ^ 0 = n u m s i 0 = nums_i 0=numsi
有了上述推导，我们只要将所有数全部都异或到初值为 0 0 0的变量 x o r xor xor中就可以在 O （ N ） O（N） O（N）的时间复杂度， O ( 1 ) O(1) O(1)的空间复杂度内得到出现了奇数次的数了。
public static void oddTimesNum(int[] arr) {
int xor = 0;
for (int num : arr) {// foreach，迭代器实现
xor ^= num;
}
System.out.println(xor);
}
只出现一次的数字 III
这是一道leetcode原题传送门清点我!!!
给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
我们首先强化一下这个命题，有两个元素出现了奇数次，其他元素都出现了偶数次，找出那两个出现奇数次的数。
在介绍这道题之前，我们先介绍一种操作，就是提取出一个数二进制中最右侧的1，比如提取出24最右侧的1
// 24
// 11000
// 提取出最右侧的1
// 01000 => 8
那么怎么完成这个操作呢？ a a a & ( a + 1 ) (~a + 1) ( a+1) 就能做到这个操作。
// 就拿a = 24举例
// a 11000
// ~a 00111
//~a+1 01000
// a 11000
// & ------------
// 01000
// 这样就取出了a最右侧的1
有了上面的铺垫我们就可以继续看这道题目了，我们先将所有数异或到初值为 0 0 0的变量 x o r 1 xor1 xor1中
x o r 1 = n u m s 1 xor1 = nums_1 xor1=nums1 ^ n u m s 2 nums_2 nums2 ^ … ^ n u m s n − 1 nums_{n - 1} numsn−1
设这两个奇数为 a a a， b b b，那么有：
x o r 1 = a xor1 = a xor1=a ^ b b b
我们继续分析，我们可以 x o r 1 xor1 xor1中最右侧的1提取出来，由于a ! = b != b !=b所以 x o r 1 xor1 xor1的二进制位中一定会有 1 1 1，比如 x o r 1 xor1 xor1的第 i i i位为 1 1 1。那么这意味这什么？意味着a和b的二进制在第i位上是不一样的，这样我们就可以用这个性质将数组中的数分为两类，一类是第 i i i位是 1 1 1的，一类是第 i i i位是 0 0 0的。我们在准备一个初值为 0 0 0的变量 x o r 2 xor2 xor2将第一类数全部异或上。我们分析下，异或后 x o r 2 xor2 xor2的值。
x o r 2 = a xor2 = a xor2=a ^ . . . . . . ...... ...... 后面可能有数可能没数，这不影响（因为它们会出现偶数次，异或后值为0）
我们发现， x o r 2 xor2 xor2的值为 a a a！！！最后我们只需要将 x o r 2 xor2 xor2和 x o r 1 xor1 xor1异或就可以得到另一个数 b b b了!!!
public static void printOddTimesNum2(int[] arr) {
// 两种数 一种为 a 一种为 b
int xor1 = 0;
for (int num : arr) {
xor1 ^= num;
}
// 此时 eor1 = a ^ b;
// 数组中所有的数可以分为两类(a != b)
// 拿到eor最右侧的1 eor & (~eor + 1) => (eor & (-eor))
// 1. 第一类rightOne a 和一些出现了偶数次的数
// 2. 第二类NonRightOne b 和一些出现了偶数次的数
int rightOne = xor1&(~xor1 + 1);
int xor2 = 0;
for(int num : arr) {
if((num & rightOne) != 0) {
xor2 ^= num;
}
}
// 此时eor1就得到了第一类数,再将xor1和xor2进行异或就可以得到第二类数了
System.out.println(xor2 + " " + (xor1 ^ xor2));
}
只出现一次的数字 II
这是一道leetcode原题传送门清点我!!!
给你一个整数数组 nums ，除某个元素仅出现 一次外，其余每个元素都恰出现三次 。请你找出并返回那个只出现了一次的元素。你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
同样，我们先强化一下这个命题，数组nums中，某个元素出现了k次，其余每个元素都出现了 m m m次，找到并返回出现了 k k k次的数。那么对于这个问题，我们又该如何取作呢？
这个问题，我们是这样考虑的，先准备一个长度为32的二进制信息数组t，将nums数组中的所有数的二进制中 1 1 1出现的次数统计到t数组中。由于 k < m k < m k<m所以对于t数组中的每一位，如果t[i]的值是对m取余等于k，说明出现了k次的数的二进制在第 i i i位上是 1 1 1。什么意思，举个例子当 k = 1 m = 3 k = 1 m = 3 k=1m=3 是就是上面这道leetcode原题，给定nums数组[2,2,3,2]，我们统计其中所有数的二进制信息得到t数组 [00000000 00000000 00000000 00000041]，其中第32位为1对 m m m（3）取模，后等于k，所以出现 k k k次的数在第32位上是1，同理第31位上也是1，最后得到出现 k k k次的数字的二进制0011，从而还原出3出现了 k k k次。
我们还可以讨论组成第 t [ i ] t[i] t[i]位的数值的情况，可能出现了 k k k次的数在这位上是 1 1 1，可能其他出现了 m m m次的数在这位上也是 1 1 1。
①： t [ i ] = k + n × m ( n t[i] = k + n \times m(n t[i]=k+n×m(n个数出现了 m m m次， n = n = n= n u m s . l e n g t h − k m nums.length - k \over m mnums.length−k),我们可以让 t [ i ] t[i] t[i] 对m取模，如果等于 k k k，则出现了 k k k次的数在第 i i i位上是 1 1 1。
②： t [ i ] = k t[i] = k t[i]=k,由于 k < m k < m k<m ，所以对 m m m取模，值还是 k = = k k == k k==k，所以现了 k k k次的数在第i位上是 1 1 1。
③： t [ i ] = n × m t[i] = n \times m t[i]=n×m,对 m m m取模后值为 0 0 0，所以现了 k k k次的数在第 i i i位上是 0 0 0。
④： t [ i ] = 0 ! = k t[i] = 0 != k t[i]=0!=k,所以现了 k k k次的数在第 i i i位上是 0 0 0。
综上，只要满足 t [ i ] t[i] t[i] % m = = k m == k m==k则出现了看次的数在第i位上是 1 1 1，从而还原出出现了 k k k次的数。
public static int OnlyKTimes(int[] arr, int k, int m) {
int[] t = new int[32];
for (int x : arr) {// foreach
for (int i = 0; i <= 31; i++) {
t[i] += (x >> i) & 1;// ①统计位1
}
}
int ans = 0;
for (int i = 0; i <= 31; i++)
if (t[i] % m == 0k) {
ans |= (1 << i);// ②设置答案
}
return ans;
}
这里留下①和②两个点读者可以自行思考。