快速比较两个值

可以用a^b == 0来快速比较两个值，效率会更高

使某些特定的位翻转

0 ^ 1 = 1

1 ^ 1 = 0

例如：翻转10100001的第6位，答案：可以将该数与00100000进行按位异或运算：10100001 ^ 00100000 = 10000001

判断一个二进制数中1的数量是奇数还是偶数

求10100001中1的数量是奇数还是偶数；答案：1 ^ 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 0 ^ 1 = 1,结果为1就是奇数个1，结果为0就是偶数个1

不使用其他空间，交换两个值

1
2
3

a = a ^ b;
b = a ^ b; //a ^ b ^ b = a ^ 0 = a;
a = a ^ b;

一个整型数组里除了N个数字之外，其他的数字都出现了两次，找出这N个数字

从{A B C B C D A}找出单个字母的D

用到：

A ^ A = 0;
异或满足交换律、结合律

A ^ B ^ C ^ B ^ C ^ D ^ A
= A ^ A ^ B ^ B ^ C ^ C ^ D
= 0 ^ 0 ^ 0 ^ D
= 0 ^ D
= D

时间复杂度为O(n)，当然是线性的，空间复杂度O(1)

int singleNumber(int A[], int n) {
    //特殊情况1,2  
    if(n<=0) return -1;
    if(n==1) return A[0];

    int result = 0;
    for (int i = 0; i < n; i ++) {
        result = result ^ A[i];
    }
    return result;
}

一个整型数组里除了两个数字之外，其他的数字都出现了两次。找出这两个只出现一次的数字

思路：

肯定还是像我们上面的解法一样，所有数进行异或，不过最终得到的结果是 a 和 b（假设 a 和 b 是落单的数字）两个值的异或结果 aXORb，没有直接得到 a 和 b 的值；
那么我们如何找到两个的真实值呢？根据异或的特点可以发现，两个相同的位异或后结果是0，不同则是1。同时aXORb不可能每一位都是0，那么就可以得知假如有一位是1的话，则对应着a与b在此位上的数值是不同的，由此我们可以根据这个特点进行解题。因为a,b不同，肯定有一个位是1，对应着那个就是0，我们可以先找出aXORb第一位为1的那个位，把它提取出来，然后其他位全为0，然后与数组所有的数进行&运算，这样就能找出与提取出的那个数（其实也只是一个位有用）的位相等的数，比如提取出的是0001，那么1111可以被&找出来。

aXORb = a ^ b，假设我们已经找到了 a，根据异或特性，我们知道，b = aXORb ^ a；这样我们就可以找出 b；所以我们只需要循环两次

#include <iostream>
#include <assert.h>
using namespace std;

int getFirstOneBit(int num) //输出 num 的低位中的第一个 1 的位置  
{
    return num & ~(num - 1);  // num 与 -num 相与找到
}

void findTwo(int *array, int length){
    int aXORb = 0;
    int firstOneBit = 0;
    int a = 0;
    int b = 0;
    for (int i = 0; i < length; i++) {
        aXORb ^= array[i];
    }
    assert(aXORb != 0); //保证题目要求，有两个single的数字，如果不成立则退出程序
    firstOneBit = getFirstOneBit(aXORb);
    for (int i = 0; i < length; ++i) {
        if(array[i] & firstOneBit)
        //与提取出的那个数对应的位相同的数有很多，但是其他的数都有相同的两个，异或后就可以相除了，只留下单独的那一个
         {
            a ^= array[i];
        }
    }
    b = aXORb ^ a;
    cout << "a: " << a << endl;
    cout << "b: " << b << endl;
}


int main()
{
    int array1[] = {2, 5, 8, 2, 5, 8, 6, 7};
    findTwo(array1, 8);
    return 0;
}