[算法]按位异或^的种种玩法

本文使用C语言

什么是按位异或^

首先将不同数制的数写成二进制,例如9->0b1001.
然后最末位对齐，依次按位异或.
规则:0 ^ 0= 0 ; 1 ^ 1 = 0; 1 ^ 0 = 1
推论:任意整数x,都有0^x = x ; x ^ x = 0\

来看看应用

寻找一个单身狗数

像[1,3,2,2,3]这样除了某一个数1,剩下的数字都是成对的,也就是说遍历一次数组，把所有的元素按位异或在一起，结果便是落单的那个1

//代码实现
int arr[] = {1,3,2,2,3};
int sz = sizeof(arr)/sizeof(arr[0]);//求数组大小
int ret  = 0;
for (int i =0;i<sz;i++)
{
    ret^=arr[i];
}

return ret; //此时ret即为落单的那个数

变形

消失的数

已知一个由0~n(缺失一个数)填充的数组，例[0,6,4,2,3,1],例中的数组少了一个5,而我们已知数组包含0~6中的5个数，就可以将数组元素与0~6按位异或到一起，将问题消失的数转化为问题寻找单身狗,消失的数变成剩下的那个单身狗

//代码实现
int missingNumber(int* nums, int numsSize)
{
    int ret = 0;
    for(int i = 0;i<numsSize;i++>)
    {
        ret^=nums[i];//历遍nums的所有元素
        ret^=i;//历遍0~numsSize-1
    }
    ret^=numsSize;//补上numsSize;
    return ret;
}

进阶

找到两个单身狗

数组再升级，单身狗变成了两个，导致不能粗暴地把所有元素按位异或来求出两个数,但我们仍可以将问题简化：能否将两个单身狗分到两个数组，使之转化为两个独立的求单个单身狗问题。于是难点来到了如何分组

方案之一便是运用按位异或和右移运算符

因为两个不同的数，在二进制上作比较，就至少有一位是不同的，以那一位为0或1分成两组，便可将两个单身狗分开.而若要查找具体是哪一位，将列表中所有元素（就包括了两数）按位异或后再用右移运算符逐位检验是否为1,之后便可轻松分组，并直接按位异或得出结果

//代码实现
int* singleNumber(int* nums, int numsSize, int ret[2]){
    int ret1 = 0;
    int ret2 = 0;
    int n = 0;//用于记录"1"在哪一位
    int tmp = 0;
    for(int i =0;i<numsSize;i++)
    {
        tmp^=nums[i];
    }
    while((tmp>>n) !=1 )
    {
        n++;
    }
    for(int i = 0; i<nums;i++>)//再次历遍
    {
        if((nums[i]>>n ==1))//分组1
        {
            ret1^=nums[i];
        }
        else  //分组2
        {
            ret2^=nums[i];
        }
    }
    ret[0] = ret1;
    ret[1] = ret2;
    return ret;
}

思考:3个，4个....N个单身狗时呢？