两数交换 —— 位运算实现

注意：两个数一定不能指向同一内存空间，不然结果都会变成0！

int a,b;
a = a^b;
b = a^b;
a = a^b;

二进制异或运算 0^1 , 0^0 , 1^1 。相同为 0 ，不同为 1 。

运用到具体两个数字上，就是相同两数异或会为 0 ， 0 再异或任何一个非零的数，就是这个数本身。

异或有交换律和结合律。

运用实战

问题1

给一个数组 arr[] ，有一种数出现了奇数次，其它数都出现了偶数次，让你把那出现奇数次的数找出来

int[] arr=new int[]{2,2,3,3,4,4,5,5,5};
int res=0;
for (int cur : arr) {
    res ^=cur;
}
return res;

给一个数组 arr[] ，有两种数出现了奇数次，其它数都出现了偶数次，让你把那出现奇数次的两种数找出来

int[] arr = new int[]{2, 2, 3, 3, 4, 4, 5, 5, 5, 6, 6, 6};
int eor = 0;
for (int cur : arr) {
    eor ^= cur;
}
//eor=a^b
//eor!=0
//eor必然有一个位置为1
int rightOne = eor & (~eor + 1);//提取出最右的1
int onlyOne = 0;
for (int cur : arr) {
    if ((rightOne & cur) == 0) { //与运算。最右的 1 只有与上 1 才能等于 1 。
        onlyOne ^= cur;
    }
}//把其中一个数提取出来了 onlyOne = a || b
System.out.println(onlyOne + " " + (eor ^ onlyOne));

• 与运算。只有两个位都等于 1 时，结果才为 1
• 或运算。只要有 1 个位为 1 ，结果就为 1
• 异或运算。如果两个位为“异”（值不同），结果就为 1 。

时间复杂度

算法在最坏情况下运行所需时间。