GroupBlog

异或运算概念和性质

在数字逻辑中，逻辑算符互斥或闸（exclusive or）是对两个运算元的一种逻辑分析类型，符号为XOR或EOR或⊕。与一般的逻辑或OR不同，当两两数值相同为否，而数值不同时为真。
两个运算元（命题）：A与B的异或一般写成A异或B，A xor B,A ⊕ B,在C或C++中，用A^B表示
其实异或其实是一种二进制不进位加法
1 + 1 = 10                      1^1 = 0
1 + 0 = 01                      1^0 = 1
0 + 1 = 01                      0^1= 1
0 + 0 = 00                      0^0 = 0
性质：
交换律： ${\displaystyle A\oplus B=B\oplus A} A\oplus B=B\oplus A$
结合律： ${\displaystyle A\oplus (B\oplus C)=(A\oplus B)\oplus C} A\oplus (B\oplus C)=(A\oplus B)\oplus C$
恒等律： ${\displaystyle X\oplus 0=X} X\oplus 0=X$
归零律： ${\displaystyle X\oplus X=0} X\oplus X=0$
自反： ${\displaystyle A\oplus B\oplus B=A\oplus 0=A} A\oplus B\oplus B=A\oplus 0=A$

异或的一些简单使用

交换

a = a ^ b;
b = a ^ b;
a = a ^ b;

第一步：a = a^b;
完成后 a变量的结果为a^b

第二步：b = a ^ b;
此时赋值号右边的a保存的是a^b的值,那么将赋值号右边的a用a^b替换，
得到(a^b)^b=a^(b^b)=a^0=a,
即经过第二步运算后b中的值为a，即b=a，将a换到了b里

第三步： a = a ^ b;
此时赋值号右边的a保存的仍然是a ^ b的值，不变，而赋值号右边的b已经是a 了，
将赋值号右边的a,b分别进行替换，
即此时赋值号右边a ^ b=（a ^ b）^ a=a ^ b^ a=a ^ a^ b=0^ b=b, 该值赋值给a,即a=b

即经过第三步运算后a中的值为b，即a=b,将b换到了a

通过引用实现的交换函数

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

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

int main() {
    int a,b;

    cin >> a >> b;

    int &x = a;
    int &y = b;
    myswap(x,y);

    cout << x << " " << y << endl;

    return 0;
}

这里写图片描述

用于查找重复元素

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现
一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空
间，能否设计一个算法实现？

方法一：
利用求和算差值

int sum = 0;
for(int i = 0;i < 1001;i++) {
    sum += s[i];
}
int res = sum - 1000*1001/2;

方法二：
利用异或运算,将所有的数全部异或，得到的结果与1^2^3^…^1000的结果进行异或，得到的结果就是重复数
先利用交换率
1^2^…^res^…^res^…^1000，无论这两个n出现在什么位置，都可以转换成为1^2^…^1000^(res^res)的形式
设1^2^3…^1000^res的结果为T
1^2^3…^1000^res的结果为T^res
那么T^(T^res)=res

实现一个加法运算

把加法的分为两个过程，一个是不进位运算，另一个是进位操作
1.不考虑进位的计算结果，以一位二进制数利用^运算
2.进位，同样以一位二进制数表示：
0+0→不进位
0+1→不进位
1+0→不进位
1+1→进位，即相当于是10，将10加到不考虑进位的计算结果上，即可得到整个的计算结果，而可以用位运算的与操作和向左的移位操作即可模拟上述的是否进位：
0&0=0         (0&0)<<1=0
0&1=0         (0&1)<<1=0
1&0=0         (1&0)<<1=0
1&1=1         (1&1)<<1=10

需要按照递归的方式将上述思想实现，主要原因是将运算结果分为不考虑进位的运算结果A和进位值B，则计算结果为A+B，但该运算可能还是会产生进位，故将A和B再次采用这种计算方法进行计算，知道进位部分为0，即表示上次加法计算没有进位，则上次加法计算的不考虑进位的运算结果，即为整个加法计算的结果。

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

int xorAdd(int x,int y) {
    if(!x) {
        return y;
    } else {
        return xorAdd((x&y)<<1,x^y);
    }
}

int main() {
    int a,b;

    cin >> a >> b;

    printf("%d %d\n",a+b,xorAdd(a,b));

    return 0;
}

这里写图片描述