位异或运算
位异或运算的规律和应用
表述
-
两个数进行位运算，相同的位数异或结果为0；不同的位数，异或结果为1。即：
0 ^ 1 1 0 ^ 0 0 1 ^ 1 0 1 ^ 0 1 -
异或运算还可以理解为 无进位相加
比如2的二进制为10，1的二进制为01，1^2的结果为3，二进制为11。那么通过这个性质可以用来判断奇数还是偶数。
规律
- 0^A=A 0异或任何数A都等于A本身
- A^A=0 任何数A异或其本身都等于0
- 异或运算满足交换律， 即A^B=B^A
- 异或运算满足结合律，即(A^B)^C=A^(B^C)
- 所有的偶数异或1的结果都是原来的数字加上1的结果。
- 所有的奇数异或1的结果都是原来的数字减去1的结果。
交换的应用
使a和b的值交换
void swap(int a, int b)
{
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
算法问题1
问题：一个数组中，只有1个数出现奇数次，其他数均出现偶数次。求出现奇数次的这个数
解：可以使数组每个元素都异或起来，最后数值即是解。
因为异或运算满足交换律和结合律，则出现偶数次的数经过异或结果为0，出现奇数次的数异或结果为其本身。
此算法的时间复杂度为O(n)，空间复杂度为O(1)
int MyFun(std::vector<int>& arr)
{
int ret = 0;
for (int it : arr)
{
ret ^= it;
}
return ret;
}
算法问题2
问题：一个数组中，只有2个数出现奇数次，其他数均出现偶数次。求出现奇数次的这2个数
解：结合上一个问题，可以知道，这个数组整体遍历异或一遍，可以消去出现偶数次的数值，假设2个待求数分别为A和B，原数组
n1^n2^n3......^nN = A^B
已知 A != B，则A和B的二进制数中至少有一位是不相等的，即假设A的二进制数第N位是1，B的第N位是0。利用此差异，可以将A单挑出来。方法是找到所有二进制数第N位是1的数，全部异或起来，得到数值A
ni^nj......nk = A (ni, nj......nk都是二进制数第N位是1的数）
求得A和A^B，使用 A ^ A ^ B = B
则得到A和B，代码如下
void MyFun(std::vector<int>& arr, int& A, int& B)
{
int ret = 0;
//求得A ^ B = ret
for (int it : arr)
{
ret ^= it;
}
//找到A和B中不相等的最低位
//相当于找A^B,即ret中等于1的最低位
//常规算法，找到一个数R中等于1的最低位，可以用 R &（R的补数）实现
const int ro = ret & (~ret + 1);
//取得A
A = 0;
for (int it : arr)
{
//挑选出指定位为1的数值，遍历异或
if (ro & it)
{
A ^= it;
}
}
//取得B
B = ret ^ A;
}