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異或等于她本身 也就是缺失的那個值，她沒有可以與之比對的值。