Find missing number in 4 billinon 32 bit integers

Oct272008

Problem
Given a file with 4 billion 32bit integers, how do you find an missing integer from the file? In other words, which integer didn't show up in this file? You are given only 16MB memory.( not using external sorting)
solution
Like 3 bits. Suppose my list has 0, 1, 2, 3, 4, 6, 7. (sorted for convenience of explanation, but that's not a requirement)
000
001
010
011
100
110
111

Now count the bits:
number of bits from most significant to least significant bit position:

msb lsb
zeros: 4 3 4
ones: 3 4 3

Since the most-significant bit position is missing a 1, the middle bit position is missing a 0, and the least-significant bit position is missing a 1, we get this number to fill in the gaps:
101, or 5 decimal.

code
#include <iostream>
#include <fstream>
using namespace std;

int main() {
unsigned int number;
int bits[2][32] = {0};
ifstream numbers_file;
numbers_file.open("numbers.txt");
int i = 0;
numbers_file >> number;
while( ! numbers_file.eof()) {
for (i =0; i<32; i++){
int shifted = number>>i;
int bit = shifted % 2;
bits[bit][i]++;
}
numbers_file >> number;
}
unsigned int missing = 0;
for (i =31; i> -1; i--){
if(bits[0][i]>bits[1][i]) missing++;
missing = (missing<<1);
}
cout << "missing number is " << missing << endl;
}