# 第2节 异或运算相关面试题
# 认识异或运算
异或运算：相同为0，不同为1 同或运算：相同以1，不同为0 能长时间记住的概率接近0% 所以，异或运算就记成无进位相加
# 异或运算的性质
0^N == NN^N == 0- 异或运算满足交换律和结合律
- 交换律：异或运算不分先后结果一样 例如：
a^b == b^a - 结合律：
(a^b)^c == a^(b^c) - 既满足交换律和结合律的结论是：
同样一批数不管是怎么的排列组合的异或顺序其结果是一样的 - 奇数个相同的数(N)异或 == N
- 偶数个相同的数(N)异或 == 0
上面的两个性质用无进位相加来理解就非常的容易
# 题目一
如何不用额外变量交换两个数
package class02;
/**
* 异或运算练习
* 如何不用额外变量交换两个数
* @author yangyanchao
*
*/
public class Test01_Swap {
public static void main(String[] args) {
int[] arr = { 3, 1, 100 };
printArray(arr);
swap(arr, 0, 1);
printArray(arr);
}
/**
* 打印数组
* @param arr
*/
private static void printArray(int[] arr) {
if(arr == null) {
return ;
}
System.out.print("{ ");
for(int num : arr) {
System.out.print(num + " ");
}
System.out.println("}");
}
/**
* 如何不用额外变量交换两个数
* @param arr
* @param i
* @param j
*/
public static void swap(int[] arr, int i, int j) {
// arr[0] = arr[0] ^ arr[0];
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
}
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
38
39
40
41
42
43
44
45
46
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
38
39
40
41
42
43
44
45
46
# 题目二
一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
package class02;
/**
* 异或运算练习
* 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
* @author yangyanchao
*
*/
public class Test02_EvenTimesOddTimes {
/**
* 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
* @param arr
*/
public static int getNumOddTimes(int[] arr) {
if(arr == null || arr.length == 0) {
return -1;
}
int eor = 0;
for(int num : arr) {
eor ^= num;
}
return eor;
}
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 2, 2, 1, 3, 1, 1, 2, 3 };
System.out.println(getNumOddTimes(arr));
}
}
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
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
# 题目三
怎么把一个int类型的数，提取出最右侧的1来，统计数N的二进制位中有几个1
package class02;
/**
* 异或运算练习
* 统计数值的二进制位中有几个1
* @author yangyanchao
*
*/
public class Test03_BitOneCounts {
/**
* 统计数值的二进制位中有几个1
* count = 0
* 先提取最右侧的1->rightOne
* 再num &= rightOne
* count++
* 再提取最右侧的1->rightOne
* @param num
* @return
*/
public static int bit1Counts(int num) {
int count = 0;
while(num != 0) {
int rightOne = num & (~num + 1);
num ^= rightOne;
count++;
}
return count;
}
public static void main(String[] args) {
System.out.println(bit1Counts(5));
}
}
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
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
# 题目四
一个数组中有两种数
(x,y)出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数解题思路：
- 定义
eor=0，遍历数组eor=x^y- 找出
eor二进制位中rightOne最右侧的1，说明x与y的二进制中在这个位置上是不同- 基于此可以将数组分为两组
x组为arr[i] & rightOne == rightOney组为arr[i] & rightOne == 0x组求eor1，遍历数组eor1=x，y= eor^eor1
package class02;
/**
* 异或运算练习
* 一个数组中有两种数(x,y)出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
*
* @author yangyanchao
*
*/
public class Test04_OddTimes {
/**
* 一个数组中有两种数(x,y)出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
* eor = 0
* eor ^= num
* eor -> x ^ y
*
* @param arr
*/
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for(int num : arr) {
eor ^= num;
}
// eor -> x ^ y
int rightOne = eor & (~eor + 1);
int eor1 = 0;
for(int num : arr) {
if((num & rightOne) != 0) {
eor1 ^= num;
}
}
System.out.println(eor1 + " " + (eor ^ eor1));
}
public static void main(String[] args) {
int[] arr2 = { 4, 3, 4, 2, 2, 2, 4, 1, 1, 1, 3, 3, 1, 1, 1, 4, 2, 2 };
printOddTimesNum2(arr2);
}
}
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
38
39
40
41
42
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
38
39
40
41
42
# 题目五
一个数组中有一种数出现K次，其他数都出现了M次， M > 1, K < M 找到，出现了K次的数， 要求，额外空间复杂度O(1)，时间复杂度O(N)
解题思路：
- 生成一个初始化
HashMap<Integer, Integer>记录key为二进制中每一位上的1其余是0的数，记录value为二进制中的哪一位置，例如二进制是0000 0000 0000 0000 0000 0000 0000 0100，则key值为二进制本身数值，value为2，因为1在2位置上- 准备int[32]数组存储原数组中所有数中的第i个二进制位上的和
package class02;
import java.util.HashMap;
import java.util.Map;
/**
* 一个数组中有一种数出现K次，其他数都出现了M次， M > 1, K < M 找到，出现了K次的数， 要求，额外空间复杂度O(1)，时间复杂度O(N)
*
* @author yangyanchao
*
*/
public class Test05_KM {
/**
* 二进制位置的反向索引
*/
public static HashMap<Integer, Integer> map = new HashMap<>();
/**
* 将二进制上32位上的1一次put到map
* key为二进制上的1
* value为索引位置 相当于反向索引
*/
public static void initMap() {
int key = 1;
for (int i = 0; i < 32; i++) {
map.put(key, i);
key <<= 1;
}
}
/**
* 请保证arr中，只有一种数出现了K次，其他数都出现了M次
* 1、任何int数值都是32位的二进制数值，所以可以定义一个int[32]bitTotal数组 每个元素存储该位置上的1的个数
* 2、遍历bitTotal数组，若每个位置上的1的个数(num) num%m !=0 ，并且 num%m == k则说明出现k次的数中该位置上是1
*
* @param arr
* @param k
* @param m
* @return
*/
public static int onlyKTimes(int[] arr, int k, int m) {
if (map.size() == 0) {
initMap();
}
// 1、任何int数值都是32位的二进制数值，所以可以定义一个int[32]数组 每个元素存储该位置上的1的个数
int[] bitTotal = new int[32];
for (int num : arr) {
while (num != 0) {
int rightOne = num & (~num + 1);
bitTotal[map.get(rightOne)]++;
num ^= rightOne;
}
}
// 2、遍历bitTotal数组，若每个位置上的1的个数(num) num%m !=0 ，并且 num%m == k则说明出现k次的数中该位置上是1
int result = 0;
for (int i = 0; i < 32; i++) {
if (bitTotal[i] % m != 0) {
if (bitTotal[i] % m == k) {
result |= (1 << i);
} else {
return -1;
}
}
}
// 3、若出现k次的值是0 需要单独遍历处理
if (result == 0) {
int k1 = 0;
for (int num : arr) {
if (num == 0) {
k1++;
}
}
if (k != k1) {
return -1;
}
}
return result;
}
/**
* 比对函数 使用了map<num,count>
*
* @param arr
* @param k
* @param m
* @return
*/
public static int compare(int[] arr, int k, int m) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : arr) {
int temp = 0;
if (map.containsKey(num)) {
temp = map.get(num);
}
map.put(num, ++temp);
}
for (int num : map.keySet()) {
if (map.get(num) == k) {
return num;
}
}
return -1;
}
// [-range, +range]
public static int randomNumber(int range) {
return ((int) (Math.random() * range) + 1) - ((int) (Math.random() * range) + 1);
}
public static void main(String[] args) {
int maxTimes = 500000;
int range = 30;
boolean succed = true;
for (int i = 0; i < maxTimes; i++) {
int k = (int)(2 * Math.random() + 1); // 随机1到3的变量
int m = (int)(2 * Math.random() + 3); // 随机3到5的变量
int kinds = (int)(4 * Math.random() + 2);// 随机2到6的变量
int[] arr = generateRandomArray(range, kinds, k, m);
if(onlyKTimes(arr, k, m) != compare(arr, k, m)) {
succed = false;
printArray(arr);
System.out.println(kinds + " " + k + " " + m);
System.out.println(onlyKTimes(arr, k, m));
System.out.println(compare(arr, k, m));
break;
}
}
System.out.println(succed ? "Nice." : "ooVoo");
}
/**
* 打印数组
* @param arr
*/
private static void printArray(int[] arr) {
if(arr == null) {
return ;
}
System.out.print("{ ");
for(int num : arr) {
System.out.print(num + " ");
}
System.out.println("}");
}
/**
* 生成数值种类为kinds 一种数出现k次数与其他数出现m次的随机数组
* @param maxValue
* @param kinds
* @param k
* @param m
* @return
*/
private static int[] generateRandomArray(int range, int kinds, int k, int m) {
int size = k + (kinds - 1) * m;
int[] arr = new int[size];
int randomVal = randomNumber(range);
for(int i = 0; i < k; i++) {
arr[i] = randomVal;
}
int temp = k;
int count = 0;
int mRandomVal = randomNumber(range);
while(temp < size) {
if(count % m == 0) {
mRandomVal = randomNumber(range);
if(randomVal == mRandomVal) {
mRandomVal += 1;
}
}
arr[temp] = mRandomVal;
count++;
temp++;
}
// arr 填好了
for (int i = 0; i < arr.length; i++) {
// i 位置的数，我想随机和j位置的数做交换
int j = (int) (Math.random() * arr.length);// 0 ~ N-1
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
return arr;
}
}
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188