找重复数的多种解法

1-1000放在含有1001个元素的数组中，只有唯一的一个元素值重复，其它均只出现一次。每个数组元素只能访问一次，设计一个算法，将它找出来；不用辅助存储空间，能否设计一个算法实现？
发起文章：算法题,求高手. 作者： 莫贝特(MBetter) 
算法改进：利用异或的特性解决，找出重复数的问题，应该是目前最优算法。  作者：Ivony...

莫贝特给出的算法是：将所有数加起来，减去1+2+...+1000的和
Ivony给出的算法是:  将所有的数全部异或，得到的结果与1^2^3^...^1000的结果进行异或，得到的结果就是重复数
两位算法的时间复杂度都是: 2n (莫贝特的算法可以用高斯算法简化)

莫贝特的代码C#：

static void Main(string[] args)
{
    int[] list = new int[1001];

    for (int i = 1; i < 1001; i++)
        list[i - 1] = i;

    Random random = new Random();
    list[1000] = random.Next(1, 1000);

    int sum1 = 0;
    int sum2 = 0;

    foreach (int i in list)
        sum1 = sum1 + i;
    for (int i = 1; i < 1001; i++)
        sum2 = sum2 + i;

    Console.WriteLine("重复的数字是:"+(sum1 - sum2).ToString());
    Console.Read();
}

鹤冲天的代码C#，消除了莫贝特代码存在溢出的可能：

public static int GetRepeated2(int[] array)
{
    int temp = 0;
    for (int i = 0; i < array.Length; i++)
        temp += array[i] - i ;
    return temp;
}

我根据异或方法写的代码C：

/* calculate 0^1^2^3^...^N
 * the theory is based on 0~3, 4~7, ...
 * every four numbers' XOR return 0 */
uint64_t multiple_exclusive_or(int num)
{
    switch (num & 0x3) {
    case 0:
        /* 0^num */
        return num;
    case 1:
        return (num-1) ^ num;
    case 2:
        return (num-2) ^ (num-1) ^ num;
    case 3:
        return 0;
    }
}

/* (T^n)^T = (T^T)^n = 0^n = n */
int get_repeated(int *array, int len, int num)
{
    int i, result = 0;
    for (i = 0; i < len; ++i) {
        result ^= array[i];
    }
    result ^= (int) multiple_exclusive_or(num);
    return result;
}

有关异或相关的详细证明见Ivony的博客和回复。当然也可以自己尝试证明。

参考链接：http://www.cnblogs.com/mqsuper/archive/2009/07/21/1527915.html

http://www.cnblogs.com/Ivony/archive/2009/07/23/1529254.html

http://www.cnblogs.com/ldp615/archive/2009/08/08/1541825.html