## [LeetCode] Missing Number

### Missing NumberGiven an array containing n distinct numbers taken from `0, 1, 2, ..., n`, find the one that is missing from the array.For example,Given nums = `[0, 1, 3]` return `2`.Note:Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

```class Solution {
public:
int missingNumber(vector<int>& nums) {
vector<int> bitCount(sizeof(int) * 8, 0);           //n + 1个数中的bit计数
vector<int> missingBitCount(sizeof(int) * 8, 0);    //n个数中的bit计数

int len = nums.size();
for(int i=0; i<len; i++){
int j = 0;
int num = nums[i];
while(num){
if(num & 1){
missingBitCount[j]++;
}
j++;
num = num >> 1;
}
}

for(int i = 0; i<=len; i++){
int j = 0;
int num = i;
while(num){
if(num & 1){
bitCount[j]++;
}
j++;
num = num >> 1;
}
}

int result = 0;
for(int i = sizeof(int) * 8 - 1; i>=0; i--){
result = result << 1;
result += bitCount[i] - missingBitCount[i];
}
return result;
}
};```

```class Solution {
public:
int missingNumber(vector<int>& nums) {
int num = 0;
int len = nums.size();
for(int i = 0; i<len; i++){
num ^= nums[i];
}
for(int i = 0; i<len + 1; i++){
num ^= i;
}
return num;
}
};```