原创不易~看完若对你有所帮助，记得点一个赞哈，这就是对我最大的支持了！

异或位运算知识

异或的口诀可以记忆为：不进位相加，就是：

0 ^ 1 = 1 // 0+1 = 1

1 ^ 0 = 1

0 ^ 0 = 0

1 ^ 1 = 0 // 1+1=10 -> 不进位是0

注意异或满足的两个重要规律：交换律与结合律

许多数一起异或，和乱序分开一部分一部分异或是完全一样的

所以就有另外一种swap代码了，我们来看下：

public static void swap(int[] arr,int a,int b){

// 另一种基于异或的swap写法

arr[a] = arr[a] ^ arr[b];

arr[b] = arr[a] ^ arr[b];// arr[b] = arr[a] ^ arr[b] ^ arr[b] = arr[a] 因为 N^N=0

arr[a] = arr[a] ^ arr[b]; // arr[a] = arr[a] ^ arr[b] ^ arr[a] = arr[b]

}
1
2
3
4
5
6
7
8
9
10
11

相关算法题

问题1

一个int数组，只有一种数出现了奇数次，其他数字都出现了偶数次，求该数字

第一个问题有异或的知识基础话非常简单，准备一个int eor = 0的数字，然后遍历和数字所有数字都异或一遍，最后eor值就是这个数字：

原理类似消消乐的感觉

问题2

一个int数组，已知有两种数出现了奇数次（两个数字不相同），其他数字都出现了偶数次，求该数字

第二个问题有些复杂，不能直接用上面的方法去进行，但是基于异或还是可以解决的。

思想：得想办法分析出两个奇数的差异，作为不相等的两个数字，肯定存在一位，奇数B此位为0，奇数A此位为1，基于位差异就可以掰开这个数组，将原先数字分成两组，一组此位为0，另一组为1，这样就变成一组数找一个奇数的问题了，

初始设置int eor = […^…] = a^b; // 遍历数组异或结果就是a^b

当然整体思想了解之后，其实细节也涉及不少位运算，例如如何定位哪一位存在差异

public static void printOddTimesNum2(int arr[]){

int eor = 0;

// eor异或数组

for(int i = 0;i < arr.length;i++){

eor ^= arr[i];

}

// eor = a^b

// eor != 0

// eor 必有一个位置上为1

int rightOne = eor & (~eor + 1); // 提取最右的1的位算法 110010 & (001101 + 000001) = 000010

int onlyOne = 0;

for (int cur:arr){

// 掰开数组

if(rightOne & cur == 0){

onlyOne ^= cur;

}

}

System.out.println(onlyOne + " " + (eor ^ onlyOne))

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37