运算规则
二进制：相同为0 相异为1
十进制：相同为0 任何数字和0异或都是它本身
不利用额外变量交换两个数
数组中一种数字出现了奇数次，其他数都出现了偶数次，怎么得到这个出现了奇数次的数
将所有的数异或 得到的结果就是这个期望的数字
异或可以使用交换律，所有出现了偶数次的数字异或是0，出现了奇数次的数字异或得到这个数字本身
0和这个数字异或还是这个数字
public class Day006_1_找到出现了奇数次的数 {
@Test
public void test01(){
int[] xx = {1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1};
int eor = xx[0];
for (int j = 1; j < xx.length; j++) {
eor = eor ^ xx[j];
}
Assert.equals(eor, 9);
}
}
数组中两种数字出现了奇数次，其他数都出现了偶数次，怎么得到这两个出现了奇数次的数
先决条件注意异或的运算规则。见上文
假设两种出现了奇数次的数字分别是 a 和 b，数组的所有元素异或得到的结果EOR = a ^ b ≠ 0
因此对于 EOR 任何一个是 1 的二进制位上，a 和 b 在这个二进制位上的数字 一个是1 另一个是0
因此如果 EOR 能只保留下一个是 1 的二进制位其余位都归零 得到一个数字 K，比如00001000
那么K & aorK & b肯定一个是1 另一个是0& 运算只有11得1 其余都得0
因此关键就是怎么得到这个数字K
很简单：一个数字的补码 & 其相反数的补码 就能够得到
比如：一个正数 & 其相反数的补码 = 正数补码是它本身 & (正数取反得到相反数的反码+1)
相关计算可以参考 001 中的举例如下
通过下面的代码可以得到 ab 中的其中一个
public class Day006_2_找到出现了奇数次的两个数 {
@Test
public void test01(){
//两个数是8和9
int[] xx = {1,2,3,4,5,6,7,8,9,9,8,7,6,5,4,3,2,1,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,8};
int eor = 0;
for (int i : xx) {
eor = eor ^ i;
}
Assert.equals(eor, 8 ^ 9);
//eor只保留一个是1的二进制位
//例如：00000001 00001000 01000000
int onlyOne = eor & (-eor);
//注意异或的运算规则，相同为0 相异为1
int one = 0;
for (int j = 1; j < xx.length; j++) {
//如果不等于0 说明是两个数字其中的一个 或者是出现了偶数次的数字 循环完毕得到ab中的其中一个
if ((xx[j] & onlyOne) != 0) {
one = one ^ xx[j];
}
}
int another = one ^ eor;
Assert.isTrue((one == 8 && another == 9) || (one == 9 && another == 8));
}
}