算法-面试题系列-异或运算
认识异或运算
- 异或运算:相同为0,不同为1
- 同或运算:相同为1，不同为0
能长时间记住的概率接近0%
所以，异或运算就记成无进位相加!
题目一
- 如何不用额外变量交换两个数
a = a^b
b = a^b
a = a^b
题目二
- 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数
image-20210515214126342
最后xor等于多少，奇数次出现的数就是这个数。 因为偶数次的数异或后的值为0 即a^a = 0
public static void printOddTimesNum1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
题目三
- 怎么把一 个int类型的数，提取出最右侧的1来
N & (~N+1)
image-20210515215228449
image-20210515215506340
题目四
- 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数！
第一步 把数组中所有的数 xor(异或) 得到一个结果 eor 则记过肯定是是奇数 a 与 奇数 b 异或的结果！因为偶数次的数异或完之后为0
第二步 找到 eor 上最后侧的1出来 ， 假设为第N位 ， 则奇数次 a 与 奇数次 b 的第N位==一定不一样== 否则这一位不可能为1
image-20210515220558959
因为 奇数次 a 与 奇数次 b 的第N位==一定不一样== ，所以a b 一定不能被分在同一个部分里面
把第N为1的部分全部异或一遍得到eor2 得到的eor2就是奇数次 a 与 奇数次 b中的其中一个数
// arr中，有两种数，出现奇数次
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，提取出来
int rightOne = eor & ((~eor)+1); // 提取出最右的1
int onlyOne = 0; // eor'
for (int i = 0 ; i < arr.length;i++) {
// arr[1] = 111100011110000
// rightOne= 000000000010000
if ((arr[i] & rightOne) != 0) {//分组中第N为1的部分异或
onlyOne ^= arr[i];
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
