问个算法方面的问题

异或

分块hash？

@skydiver 能详细点吗？
@dennisyang 这个是今天的面试题，我也是这么说的，面试的人说有更简单的。

@john990 所有的数字异或到一起。重复的数字异或到一起就变成0了，剩下的就是多出来的数。
这是一个经典的面试题啊。。

@skydiver oh，明白了，谢谢了，看来算法是硬伤啊

@john990 这个题基本也考不了什么能力，知道就是知道，不知道就是不知道……拿这个题考人的公司感觉不怎么靠谱……

为什么会多了一个？

@skydiver 基本上G，M等家都问这种数学类型的题目。

http://oj.leetcode.com/problems/single-number/ 常目

对啊，为什么会多一个，搞清楚这个问题价值会更大吧。

把所有的数异或一下 最后的结果就是那个多出来的数
简单的面试题

sum(一百万零一个) - sum(一百万个数)

得到的结果就是多的那一个

效率是O(n)

@stevenyou 嗯，好办法

@stevenyou 有overflow的风险
@john990

@cassyfar 是有overflow的问题，但是从两个数可以看出来的。如果是32bit int
sum(一百万零一个) = -32768
sum(一百万个数) = 32767
可以知道多出的那个数是1

当然了，xor的方法是最好的。

@cassyfar sorry , 16bit int

@stevenyou 对啊 但是如果overflow之后又overflow就麻烦了 毕竟100万个数的和是个很大的和

@cassyfar
@stevenyou
实际上 overflow 没有影响，2's complement 表示的整数是个阿贝尔群。
以下代码在 32bit 上运行， sizeof(int)=4

~ cat test.c
#include <stdio.h>
int main() {
int a = 1234567890;
int b = 2134567890;
printf("%d\n", a + b);
printf("%d\n", a + b - a);
}
~ gcc -o test test.c
~ ./test
-925831516
2134567890

@stevenyou 确实没影响 只要差值保留住就可以了 和overflow多少次无关