一个整形数组A[1...n]包含0~n中的n个数，有一个数丢失。规定不可以通过A[i]获取对应的整数，可以使用的唯一的操作是fetch(i, j)，该函数表示获得A[i]的第j个bit的值（即二进制形式中的第j个bit）。假定fetch(i, j)的操作是常数的，如何在O(n)的时间内找出丢失的整数。
思路：
从0到n一共n+1个整数，用N0表示这n+1个整数中最低有效位为0的整数个数，用N1表示这n+1个整数中最低有效位为1的整数个数，那么N0和N1可能有一下两种关系：N0 = N1 或 N0 = N1 + 1。
如果丢失的数为奇数，则有：N0 = N1 + 1 或 N0 = N1 + 2，即：N0 > N1。如果丢失的数为偶数，则有：N0 = N1 - 1 或 N0 = N1，即：N0 <= N1。所以通过N0和N1的关系就可以确定丢失的整数的最低有效位是0还是1，这样就可以淘汰一半的整数。然后检查次低有效位的数字、第三低有效位的数字等等，以此类推就可以得到丢失的数字。
int FindMissing(const vector< vector<int> >& v)
{
vector<bool> flag(v.size(), 0);
vector<int> miss;
for (int j = 0; j < 32; ++j)
{
int n0 = 0, n1 = 0;
for (int i = 0; i < v.size(); ++i)
{
if ((flag[i] == false) && (fetch(i, j) & 1 == 1))
++n1;
else if ((flag[i] == false) && (fetch(i, j) & 1 == 0))
++n0;
}
if (n1 >= n0)
{
for (int k = 0; k < v.size(); ++k)
{
if ((flag[k] == false) && (fetch(k, j) & 1 == 1))
flag[k] = true;
}
miss.push_back(0);
}
else
{
for (int k = 0; k < v.size(); ++k)
{
if ((flag[k] == false) && (fetch(k, j) & 1 == 0))
flag[k] = true;
}
miss.push_back(1);
}
}
int res = 0;
for (int i = 0; i < miss.size(); ++i)
{
if (miss[i] == 1)
res |= (miss[i] << i);
}
return res;
}