Given a list of Integer (整数)[a1,a2,…,an−1,an], let x be the XOR summation of the list of integers x=a1⊕a2…⊕an−1⊕an , and then we put x into the list. Shuffle the list randomly
Now when we pick the first element or a random element from the list, we are sure it is the XOR summation of the rest of the integers
Proof using Cases and Self-inverse, Own-Inverse and Commutativity (交换律). There are 2 possible outcomes of picking a random integer from the list
x, x is the XOR summation by definition
a1, a1 is an integer that is in the given list
For a1 to be the XOR Summation of the rest of the elements, it must fulfil the following a1=a2⊕…⊕an−1⊕an⊕x
We can expand the x at the RHS, and we get (a2⊕…⊕an−1⊕an)⊕(a1⊕a2…⊕an−1⊕an)
We can re-arrange the RHS with commutativity, and we get a1⊕a2⊕a2…⊕an−1⊕an−1⊕an⊕an
With Self-Inverse and Own-Inverse, we can reduce the RHS to a1
Since RHS is equal to LHS, a1=a2…⊕an−1⊕an⊕x is valid. Thus a1 is the XOR summation of the rest of the elements
Given a⊕b, we can get back a by a⊕b⊕b . Because b⊕b=0 based on Self-Inverse, and a⊕0=a based on Own-Inverse
Swapping values without introducing a new variable
public class MyClass { public static void main(String args[]) { int x=10; int y=25; x = x ^ y; // x ^ x = y, x ^ y = x y = x ^ y; // x x = x ^ y; // y System.out.println("x: " + x); System.out.println("y: " + y); }}