异或相关知识

基本性质

0^0 = 1^1 = 0

0^1 = 1^0 = 1

x^0 = x 且 x^x = 0
交换律：x^y = y^x
结合律：(x^y)z = x^(yz)
自反性：x^yy = x

[交换两个数]

int swap(int &a,int &b)
{
    a = a^b;
    b = a^b;
    a = a^b;
}

[A集合里拿掉数x得到B集合，求x]

令XOR(X)表示将X集合内所有的数做异或

XOR(B)^XOR(A) = XOR(B)^XOR(B)x = 0^x = x

[集合A里只有数x出现1次，其余数全都重复出现2次，求x]

xor(A) = x^yy^…z^z = x^(yy^…z^z) = x^0 = x

[集合A[1_{n]里只有数x(1}n之间)出现2次，其余数1次，求x]

相当于x出现了3次,x^xx = x,

其他数出现了两次,x^x = 0

public int FindDuplicate(int[] nums) {
 int res = 0;
 for(int i = 0; i < nums.Length; i++){
     res ^= nums[i];
     res ^= i;
 }
 return res;
}

异或相关知识

原文：https://www.cnblogs.com/xiaoxiao179/p/13622682.html