2020-08-05

异或（^）运算以及leetcode对应题目268:缺失的数字

1.异或

属于二进制位运算，每位如果值相同返回0，不同则返回1.

（1）使得位置翻转（与全1异或）

exam：0011 ^ 1111 ----> 1100

（2）保留原来的值(与全0异或）

exam： 0011 ^ 0000 ----> 0011

（3）交换两个数的值而不用采用临时变量

int a=3,b=4;

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

/***原理： 
        第二步：b = b ^ a(是第二步中的a) = 第一步中的：b = b ^ a(第一步的a) ^ b = a ^ 0 = a（第一步的a）
        最后a的值同理可得


⚠️：本质上是依据了异或符号符合交换律
        
***/
           

leetcode 268 缺失的数字:

（1）思路一：进行两层遍历，外层是0-n，内层是对数组进行遍历查找，直到找不到返回外层循环的数； 

      缺点：效率太低；

（2）思路二：对0-n进行求和，然后减去数组中每一个数，剩下的值就是要求的值；

      缺点：求和可能会溢出

（3）思路三：采用异或方法，简单快捷。

int missingNumber(int* nums, int numsSize){
    int res = numsSize;
    for(int i = 0; i<numsSize; i++){
        res ^= nums[i];
        res ^= i;
    }
    return res;
}
           

解释：首先理解题目：数组有n-1个数字，我们需要从中找到少了0-n中的哪一位数字。

这里用到了上面说到的异或符合交换律，代码中最重要的是不要忽略了res的初值要赋值为numSize；

以长度为3的数组为例：

res= numSize(即3) ^ nums[0] ^ 0 ^ nums[1] ^ 1 ^ nums[2] ^ 2

那么根据交换律，在0-n中的数字都会异或结果等于0，剩下的与0异或等于她本身 也就是缺失的那个值，她没有可以与之匹配的值。