异或的几个作用

0. 一个整数N的二进制表示中有多少个1，最低位的1出现在第几个位置。

1. 交换两个整数而不必使用第三个参数

a=9;
b=11;
a=a^b;
b=a^b;
a=a^b;
//a=11,b=9;

2. 使用异或来判断一个二进制数中的1的数量是奇数还是偶数。

• 求10100001中的1的数量是奇数还是偶数;1⁰1⁰0⁰0^1 =1，结果为1就是奇数个1，结果为0就是偶数个1;应用：这条性质可以用于奇偶校验(Parity Check),比如在串口通信中，每一个字节的数据都计算一个校验位，数据和校验位一起发送出去，这样接收方可以根据校验位粗略的判断接收到的数据是否有误。

3. 快数比较两个值

• 判断两个int型数字是否相等，你肯定会想到判断(a-b)==0(使用a==b和a^b == 0的效果是一样的。)，但是使用a^b==0效率会更高。

4. 在汇编中经常使用：xor a,a将变量置零

5. 校验和恢复

• 校验和恢复主要利用的了异或的特性：IF a ^ b = c THEN a ^ c = b
  应用：一个很好的应用实例是RAID5，使用3块磁盘（A、B、C）组成RAID5阵列，当用户写数据时，将数据分成两部分，分别写到磁盘A和磁盘B，A ^ B的结果写到磁盘C；当读取A的数据时，通过B ^ C可以对A的数据做校验，当A盘出错时，通过B ^ C也可以恢复A盘的数据。RAID5的实现比上述的描述复杂多了，但是原理就是使用 异或，有兴趣的同学看下RAID5

6. 互换二进制数的奇偶位

• 写一个宏定义，实现功能位将一个int型的数的奇偶位互换如00000110(6)->00001001(9)输出为9.

#define N(n) ((n<<1)&(0xAAAA)) | ((n>>1)&(0x5555))

7.最常出现的面试题: 一个整形数组里除了N个数以外，其他的数都出现了两次，找出这N个数。

• (1):题目(LeetCode中通过率最高的一道题)Single Number:Given a array of integers,every element appears twice except for one.Find that single one.
  由于异或的交换律(a^ b ^ c ^ d = a ^b ^ d^c),所以对于上题对整个数组中的每一个数进行异或操作，结果就是那个剩余的为单的数字。（A ^B ^C ^B ^C ^D ^D = A ^B ^B ^C ^C ^D ^D）.

• (2): 一个整型数组里面除了两个数之外，其他的所有的数字都出现了两次。
  第一步：假设为a,b对所有数字异或之后得到的结果就是a^b的结果。
  第二步：想办法得到a或者b，假设a^b为00001001，值为1的位表示a和b在这一位上不同，如上则表示a和b在最低位上不同。所以我们找出所有最低位为1的数进行异或，得到的就是a或者是b。
  第三步：假设我们已经找到了a，则b=a^(ab),这样我们就找到了b,所以我们需要循环两次；

//宏定义，用来找出某个数第一次bit为1的地方、
//如 10010110 则运算结果为 00000010
#define  getFisrtOneBit(N) ((N) & ~(N-1))

int findTwo(int *array,int len)
{
    int i = 1;
    int aXORb = array[0];
    int a = 0;
    int b = 0;
    int firstOneBit = 0;
    for (; i < len; ++i)
        aXORb^=array[i];

    if (aXORb==0)
        return 0;
    firstOneBit = getFisrtOneBit(aXORb);

    for (i = 0; i < len; ++i){
        if(array[i] & firstOneBit)
            a^=array[i];
    }
    b = aXORb^a;
    printf("%d\n", a);
    printf("%d\n", b);
    return 0;
}

• (3): 一个整型数组里除了三个数之外，其他的数字都出现了两次，请写程序找出这三个只出现一次的数字。
  第一步：像上面一样全部进行异或 则得到result = X^ Y ^Z；
  第二步：把问题简化为：假设一个数组中有三个不同的数字X,Y,Z；已知result = X ^Y ^Z,求X，Y，Z？
  1). 假设X^ Y^ Z = 0；则XYZ三个数的低位第一位为1的位置有两个数相同，一个不同。例如：X:00001000，Y:00000100，Z:00001100 Y和Z的低位第一位都是00000100,X的低位第一位是00001000;
  2). (result^ X)^ (result^ Y)^ (result ^Z) = 0;所以三个数(result ^X)、(result Y)、(result^ Z)的低位第一位为1的位置有两个相同，一个不同；那么我们获取这三个数的低位第一位为1的位置后，进行异或并取低位第一位为1的位置，就可以找到三个中"一个不同"的低位第一位为1的位置，假设这个值为firstOneBit。
  3). 遍历这三个数(result^ X),(result ^Y),(result ^Z),如果发现某个数的异或result等于firstOneBit,那么这个数就是"一个不同"的那个数。
  4). 找到了一个数，剩下的两个数，就可以通过上面的方法找出。
  第三步：完成第二步的简化后，回到原题，我们的原题比简化的问题多了一个成对的数据干扰，我们可以使用异或出去干扰数据。

#define  getFisrtOneBit(N) ((N) & ~( (N)-1))

int findOne(int *array,int len)
{
    int aXORbXORc = 0;
    int c = 0;
    int firstOneBit = 0;
    for (int i = 0; i < len; ++i)
        aXORbXORc ^= array[i];

    for (int i = 0; i < len; ++i)
        firstOneBit ^= getFisrtOneBit(aXORbXORc ^ array[i]);
    //使用异或会排除掉不相干的元素

    firstOneBit = getFisrtOneBit(firstOneBit);
    //获取到最低位

    for (int i = 0; i < len; ++i){
        if (getFisrtOneBit(aXORbXORc ^ array[i]) == firstOneBit){
            c ^= array[i];
        }
    }

    printf("C:%d\n",c);
    return c;
}

int findTwo(int *array,int len)
{
    int i = 1;
    int aXORb = array[0];
    int a = 0;
    int b = 0;
    int firstOneBit = 0;
    for (; i < len; ++i)
        aXORb ^= array[i];

    if (aXORb == 0)
        return 0;
    firstOneBit = getFisrtOneBit(aXORb);

    for (i = 0; i < len; ++i)
    {
        if(array[i] & firstOneBit)
            a^=array[i];
    }

    b = aXORb^a;
    printf("%d\n", a);
    printf("%d\n", b);
    return 0;
}

int findThree(int *array,int len)
{
    int tmpInt = findOne(array,len);
    int *tmpBuf = (int *)malloc((len+1)*sizeof(int));
    
    for (int i = 0; i < len; ++i)
        tmpBuf[i] = array[i];
    tmpBuf[len] = tmpInt;

    findTwo(tmpBuf,len+1);
    free(tmpBuf);
    return 1;
}