异或技巧

交换

交换int a 和 int b的位置

int a = 10;
int b = 20;

a = a ^ b;
b = a ^ b;	//b = a ^ b ^ b = a
a = a ^ b;	//a = a ^ b ^ b(a) = b 

a和b不能是同一个数（内存意义上），否则结果会是0

数组查找一个有奇数个的数字（其余全偶数个）

• ^具有交换律：a ^ b = b ^ a
• 偶数个某数异或等于0：a ^ a ^ a ^ a = 0
• 奇数个某数异或等于本身：b ^ b ^ b = b

void printOddTimesNum1(int[] arr){
    int eor = 0;
    for (int i = 0; i < arr.length(); i++){
        eor = eor ^ arr[i];
    }
    cout << eor << endl;
    return ;
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

查找两个有奇数个的数字

void printOddTimesNum2(int[] arr){	//arr中有奇数个a和奇数个b
    int eor = 0;
    for (int i = 0; i < arr.length(); i++){
        eor = eor ^ arr[i];	//eor = a ^ b
    }
    int rightOne = eor & (~eor + 1);	//eor中最右侧一位1，即a和b不同的一位1
    int eor2 = 0;
    for (int i = 0; i < arr.length(); i++){
        if ((arr[i] & rightOne == 0)){
            eor2 = eor2 ^ arr[i]; 
        }
    }
    int a = eor2;
    int b = eor2 ^ eor;	//a ^ (a ^ b)
    cout << a << " " << b << endl;
    return ;
}

• 其中int rightOne = eor & (~eor + 1);的原理：
  • 假设a = 1101110010
    b = 0010101010
  • eor = 1111011000
  • ~eor = 0000100111
  • ~eor + 1 = 0000101000
  • eor & (~eor + 1) = 0000001000