Missing sequence number problem solved with XOR

Question

I'm trying to understand how the XOR operation managed to solve the problem PermMissingElem

I know one of the properties of XOR is that:

A ⊕ B = C
C ⊕ A = B
C ⊕ B = A

>>> 3 ^ 4
7
>>> 7 ^ 3
4

This can be repeated for any number of operations, in this case it was 2 numbers, but it could be 3, 4, 5... n

Another property is that:

A ⊕ A = 0
A ⊕ 0 = A

>>> 3 ^ 3
0
>>> 3 ^ 0
3

But looking at the problem PermMissingElem how was it possible to guarantee that the last operation would be exactly the number that was missing? Is there any literature on this algorithm, has anyone talked about it?

A = [1,2,3,4,5,7,8,9,10,11]

missing_element = len(A)+1

for idx,value in enumerate(A):

    print(missing_element, value, (idx+1), ' = ', missing_element ^ value ^ (idx+1))
    missing_element = missing_element ^ value ^ (idx+1)  

out

11 1 1  =  11
11 2 2  =  11
11 3 3  =  11
11 4 4  =  11
11 5 5  =  11
> 11 7 6  =  10
10 8 7  =  5
5  9 8  =  4
4 10 9  =  7
> 7 11 10 =  6

as can be seen:

11 ⊕ 7 ⊕ 6 = 10
7 ⊕ 11 ⊕ 10 = 6

Answer 1

The XOR of the positive integers [1...(N+1)] is some constant:

C = 1 ⊕ 2 ⊕ ... ⊕ N ⊕ (N+1)

We can XOR both sides by the missing value, M:

C ⊕ M = (1 ⊕ 2 ⊕ ... ⊕ N ⊕ (N+1)) ⊕ M

Then we can rewrite the RHS in terms of the array A:

C ⊕ M = A[0] ⊕ A[1] ⊕ ... ⊕ A[N-1]

Finally, we can XOR both sides by C to get:

M = (A[0] ⊕ A[1] ⊕ ... ⊕ A[N-1]) ⊕ (1 ⊕ 2 ⊕ ... ⊕ N ⊕ (N+1))

Or rearranging,

M = ((A[0] ⊕ 1) ⊕ (A[1] ⊕ 2) ⊕ ... ⊕ (A[N-1] ⊕ N)) ⊕ (N+1)

Note that + could have been used instead of XOR for this solution (just need to be careful to avoid int overflow).