addition and subtraction are fine, but real men^{1} use xor...

See, the problem with summing the numbers from 1 to N-1, or 1 to N+1, is that if your list is, say, 1 to 1 billion, and you are dealing with 32-bit integers, you can add, add, add, right along, until you hit the ceiling of what a 32-bit integer can store, then POW! Like a clogged toilet when you try to flush it, overflow. And overflow is bad.

Ok, so overflow is bad. How do we avoid it? Well, you could start playing games like, "add the first element in the list, then subtract 1. Add the second element in the list, and subtract 2. Add ....", and so on. The problem is, no matter what algorithm you use, it is always possible to construct a case that results in over- (or under-) flow.

... Or, you could use the magical xor. If you can swap with it, why shouldn't you be able to find missing list elements with it? Well, you can, and it's no more complex to do that the addition/subtraction solution.

Step 1: XOR together all the numbers in the list.

Step 2: XOR that result with the XOR of all the numbers that you expect to be in the list. (1 to N-1, or 1 to N+1, depending on the problem.)

Step 3: there is no step 3; what you're left with is your answer.

How does it work?

Well, N xor N is 0, 0 xor N, and xor (the operation) is commutative, so after you xor together the range 1 to N-1 or N+1 and the list, you get a whole bunch of zeros, xored with the missing (or duplicate) element, you're done, and you haven't overflowed.

^{1}or women.. whatever.