查找连续序列缺失值

问题描述：给定n-1个整数的未排序数组，元素都是1~n的不同整数。寻找序列中缺失的整数。

思路：累加求和。首先求出数组的和sum，1~n的累加和(n+1)*n/2，而数组的缺失值就是二者之差。

int getMissing(int a[], int len)
{
  int sum = 0;
  
  for(int i = 0; i<len; i++)
    sum+=a[i];

  return (len+1)*len/2 - sum;
}

两个tips：

• 如何不使用临时变量，交换两个数

异或的两条性质： k^k = 0, k^0 = k. 同时也满足交换律和结合律
a = a^b; 
b = a^b; // b = (a^b)^b = a^(b^b) = a^0 = a
a = a^b; // a = (a^b)^a = (a^a)^b = 0^b = b

• 如何求两个大数的平均值，比如两个数的和太大，超出内存范围。

还是异或
(x&y)+((x^y)>>1)
// x&y 取出x与y二进制中都为1的所有位
// x^y 表示x与y中有一个是1的所有位，右移1位表示除以2