A solution to the mongoDB puzzle (http://goo.gl/A35lk)

GetDuplicateAndMissing.cs

//
// Given an array of N (can be very large) 64 bit integers where every integer 1-N
// appears once in the array, except there is one integer missing and one integer 
// duplicated, find the missing and duplicated integers. The algorithm should run 
// in linear time and in small constant space and leave the array untouched.
// 

static void GetDuplicateAndMissing(long[] a, out long duplicate, out long missing)
{
    long xor = 0; // duplicate ^ missing
    long diff = 0; // duplicate - missing

    for (long i = 0; i < a.Length; i++)
    {
        long index = i + 1;
        xor ^= index ^ a[i];
        diff += a[i] - index;
    }

    int bit;
    for (bit = 1; (xor & bit) == 0; bit <<= 1) { }

    duplicate = 0;

    for (long i = 0; i < a.Length; i++)
    {
        var tmp = i + 1;
        if ((tmp & bit) != 0)
        {
            duplicate ^= tmp;
        }

        tmp = a[i];
        if ((tmp & bit) != 0)
        {
            duplicate ^= tmp;
        }
    }

    missing = duplicate ^ xor;
    duplicate = diff > 0 ? Math.Max(duplicate, missing) : Math.Min(duplicate, missing);
    missing = duplicate ^ xor;
}