阿源的知识库异或运算相关面试
1. arr中只有一种数，出现奇数次
- 1111 22 3333 444
- 相当于偶数次的异或后都为0，最后只剩了一个4
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}2. 提取一个二进制最右边的1
- a & （-a）
3. arr中有两种数，出现奇数次
- 一定有两个数a,b，有eor=a^b
- eor一定不为0，我们取最右边的1
- 该位上a与b的数值一定不一样，比如这是第三位
- 那么把整个数组该位上有1的分为一组，无1的分为一组
- 令新的变量eor1去异或有1的一组，一定可以得到一个数
- 最后 eor ^ eor1
java
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// a 和 b是两种数
// eor != 0
// eor最右侧的1，提取出来
// eor : 00110010110111000
// rightOne :00000000000001000
int rightOne = eor & (-eor); // 提取出最右的1
int onlyOne = 0; // eor'
for (int i = 0 ; i < arr.length;i++) {
// arr[1] = 111100011110000
// rightOne= 000000000010000
if ((arr[i] & rightOne) != 0) {
onlyOne ^= arr[i];
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}4. 一个数组中有一种数出现K次，其他数都出现M次，K<M，求小的那个数
- 转换为32位
- 比如多的数出现了7次，若位运算后第0位上的数字是7的整数倍，那么那个较小的数该位上一定为0
java
// 请保证arr中，只有一种数出现了K次，其他数都出现了M次
public static int onlyKTimes(int[] arr, int k, int m) {
if (map.size() == 0) {
mapCreater(map);
}
int[] t = new int[32];
// t[0] 0位置的1出现了几个
// t[i] i位置的1出现了几个
for (int num : arr) {
while (num != 0) {
int rightOne = num & (-num);
t[map.get(rightOne)]++;
num ^= rightOne;
}
}
int ans = 0;
for (int i = 0; i < 32; i++) {
if (t[i] % m != 0) {
if (t[i] % m == k) {
ans |= (1 << i);
} else {
return -1;
}
}
}
if (ans == 0) {
int count = 0;
for (int num : arr) {
if (num == 0) {
count++;
}
}
if (count != k) {
return -1;
}
}
return ans;
}